Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ ГРАФОВ СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ ЛЕКЦИЯ 20 С.В.ЧУМАЧЕНКО Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 2 Тема: Способы представления графов Цель лекции – исследование способов представления графов для анализа графовых отношений и их аналитического описания Содержание: Матричные способы задания графов: матрицы смежностей, инциденций и циклов Алгебраическая форма представления графов Кубическая форма представления графов

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 3 Базовые понятия: множество граф бинарное отношение смежность инцидентность цикл матрица Термины Ключевые слова: матрица смежностей матрица инциденций матрица циклов алгебраическая форма представления графов (АФПГ) кубическая форма представления графов (КФПГ)

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 4 Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, С Харари Ф. Теория графов: Пер. с англ. / под ред. Гаврилова. М.: Мир, С , Новиков Ф.А. Дискретная математика для программистов. С.-П., С Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу Дискретна математика. Харків, ХНУРЕ с. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, С , Литература

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 5 n Основные принципы теории графов используются при построении математической модели для проектирования и анализа сетей ЭВМ n Наиболее удобной моделью сети является графовая структура n Описание графовой структуры должно быть технологичным для машины n Матричная форма является удобной для представления графов n Матрицы позволяют раскрыть структуру графа n Матрицы инциденций и циклов используются при исследовании электрических цепей, входят в качестве коэффициентов в уравнение Кирхгофа, описывающее цепь n Матрицы смежностей служат основой подхода к описанию и анализу модели компьютерной сети Актуальность и практическая направленность. 1

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 6 Актуальность и практическая направленность. 2 n Базовые сетевые топологии типа «кольцо», «звезда», «шина» и соответствующие им графы

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 7 n Матрица смежностей двумерная таблица C=||c ij || размера n n, где n число вершин, элемент которой определяется как n Пример Матрица смежностей

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 8 n Для неориентированного графа матрица смежностей является симметричной n Для ориентированного свойство симметрии не обязательно. Элемент матрицы определяется как n Суммы элементов матрицы смежностей по строкам равны степеням соответствующих вершин графа Матрица смежностей: свойства

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 9 n Матрица инциденций B=||b ij || ориентированного графа G= без петель, где |V|=p, |U|=q, есть матрица размера p q, элемент которой определяется следующим образом: n Пример Матрица инциденций

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 10 Матрица циклов Z=||z ij || графа матрица размерности m n, m количество циклов, n число ребер, элемент z ij которой определяется так n Пример Матрица циклов x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 11 n Пример Неоднозначность представления графа матрицей циклов

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 12 n По матрице смежностей можно однозначно восстановить граф: n Матрица инциденций однозначно представляет граф: n По матрице циклов нельзя однозначно восстановить граф: если ребро не принадлежит ни одному циклу, то по матрице циклов нельзя сказать, принадлежит ли оно графу Сравнение матричных способов представления графов Матрица цикловГрафМатрица смежностиГрафМатрица инциденцийГраф

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 13 n Выбор наилучшего представления определяется требованиями конкретной задачи n Используются комбинации или модификации известных представлений n Способы представления графов в памяти компьютера различаются объемом занимаемой памяти и скоростью выполнения операций n Для матрицы смежностей сложность представления определяется как О(n 2 ), где n количество вершин в графе n Для матрицы инциденций сложность определяется как O(nm), где n,m число вершин и ребер соответственно Сложность матричных способов представления графов

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 14 Time-Out

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 15 Свойства модели: компактность представления информации о графе; привязка к распространенному математическому аппарату; наличие эффективных методов анализа графовых отношений; возможность аналитического описания функций и структур. Вершины графа и переменные в булевой алгебре связаны между собой системой отношений Аппарат булевой алгебры может быть применен для описания графовых структур Алгебраическая форма представления графов (АФПГ)

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 16 Ориентированный граф G= есть множество вершин H={H 1, H 2, H 3, …..., H n }, которые связаны между собой отношениями, идентифицируемыми совокупностью дуг E={E 1, E 2, E 3, …..., E k }, где каждая дуга задается конкатенацией двух соединенных между собой вершин и обозначается в виде E r =H i &H j, или H i H j, или H i H j, или H i H j. n Ориентированная дуга E r =H i &H j, связывающая две вершины в графе, где H i – исток, H j – сток, называется импликативным отношением. HiHi HjHj ErEr АФПГ: основные положения. 1

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 17 Если, – множества вершин или дуг, принадлежащих графу G, то есть дизъюнкция или объединение этих множеств Символ вершины H i H есть формула АФПГ Символ 1 есть обозначение псевдовершины и является также формулой АФПГ Если, – формулы АФПГ, то и также являются формулами АФПГ Формулы используют открывающую и закрывающую скобки n Упорядоченная совокупность вершин, соединенная знаками импликации, называется термом АФПГ n Алгебраической формой представления графа являются выражения, построенные в соответствии с указанным выше определением АФПГ: основные положения. 2

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 18 Аксиомы АФПГ Коммутативность: для неориентированных = Ассоциативность: ( =, ( = Дистрибутивность: ( = (, ( = (, Идемпотентность: n Аксиома о единичном элементе:

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 19 Тождества АФПГ. 1 Правило поглощения (минимизации) фрагмента графа Если есть выражения АФПГ, описывающие два фрагмента графа, то действительными являются следующие уравнения: Следствие: если, – вершины графа, то дуга поглощает любую вершину, входящую в нее

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 20 Правило конкатенации (подстановки, сцепления) Если,, есть выражения АФПГ, то действительно следующее уравнение: = Тождества АФПГ. 2

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 21 Тождества АФПГ. 3 Правило разложения (декомпозиции): Если есть выражения АФПГ, являющиеся компонентами или буквами терма, то его можно разложить на два терма по любой букве (переменной), входящей в исходное выражение: Критерий смежности вершин: Неориентированный граф можно представит в виде расширения ориентированного. Если две вершины являются смежными, то для ориентированной структуры данное обстоятельство предполагает наличие двух дуг.

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 22 n АФПГ представляет удобную форму для решения задачи нахождения покрытия путями всех вершин в орграфе. Для структуры, представленной на рисунке, решение такой задачи приводит к следующему конечному результату: Пример

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 23 АФПГ есть универсальный математический аппарат для аналитического (компактного) представления графовых структур, включающих фрагменты с ориентированными, неориентированными дугами или без них. АФПГ модель, обладающая следующими свойствами: компактность представления информации о графе; привязка к распространенному математическому аппарату; наличие эффективных методов анализа графовых отношений; возможность аналитического описания функций и структур АФПГ: выводы

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 24 Кубическая система представления графов n Недостатком матричного (табличного) способа представления является большая размерность n Двухтактное кубическое исчисление (ДКИ) пригодно не только для описания функций, но и графовых структур n ДКИ используется для табличного и компактного описания орграфов или графов переходов автомата с помощью кубической формы представления графов (КФПГ) n Практическая польза введения КФПГ заключается в непосредственном использовании автоматных переменных для кодирования вершин-состояний графа

Способы представления графов Февраль, 2004 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 25 Тест-вопросы 1.В АФПГ аксиома о единичном элементе формулируется следующим образом: а) б) в) г) 2. Â АФПГ èìååò ëè ìåñòî ñâîéñòâî êîììóòàòèâíîñòè îòíîñèòåëüíî îïåðàöèè êîíêàòåíàöèè äëÿ îðèåíòèðîâàííûõ ãðàôîâ? à) äà á) íåò. 3. Ïðàâèëî ìèíèìèçàöèè ôðàãìåíòà ãðàôà: а) б) в) 4. Являются ли графы равными: 5. Если две вершины соединены одной дугой, они называются а) инцидентными б) смежными