Топология графа

Лекции по Дискретной математике Лекция 6 Топология графа. Представление графов Топология - раздел математики, исследующий идеи непрерывности (связности) представлений Изображение пространственного графа на некоторой поверхности называется укладкой Поверхности для укладки - Плоскость - Сфера - Тор - Лист Мёбиуса - Бутылка Клейна Плоская укладка графа V={1, 2, 3, 4, 5, 6, 7, 8} E={12, 13, 24, 34, 35, 46, 56, 57, 68, 78} Плоские графы n Граф, который можно уложить на плоскости без пересечения ребер, называется планарным n Плоская укладка планарного графа называется плоский граф планарный граф плоский граф Неплоские графы К5 К3,3 Структура плоского графа n Часть плоскости, ограниченная простым циклом плоского графа и не содержащая внутри других циклов называется гранью. n Число граней является инвариантом графа. n Множество ребер, ограничивающих грань называются краем грани. n Одно ребро может принадлежать максимум двум граням. n Ровно одна грань плоского графа является бесконечной (внешней). a n 4 5 m b g l c k i 3 h 2 j d f 1 e n Грани графа: {1, 2, 3, 4, 5} 1 - {ab, ac, cd, de, ef, fg, ga} 2 – {gk, kd, de, ef, fg, ki, ih, ij} 3 – {ck, kd, cd} 4 – {ab, bc, ck, kg, ga, ml, ln, nm} 5 – {ml, ln, nm} n Внешняя грань: 1 Формула Эйлера n Количество граней в любой плоской укладке планарного графа, имеющего n вершин, m ребер и k компонент связности, равно m – n + k + 1. Следствие 1: при n>2 m <= 3(n - 2) Следствие 2: при n>2 и отсутствии циклов длины 3 (триангуляций) m <= 2(n - 2) Инвариантность числа граней 6 4 5 {1,2,4,6} – внешняя 3 1 n Грани: {1,2,3}, {4,5,6}, {1,3,2,4,5,6} 2 6 4 5 1 {1,3,2,4,6} - внешняя 2 3 n Грани: {1,2,3}, {4,5,6}, {1,2,4,5,6} Критерии планарности графов n Характеристика Эйлера Граф планарен, если |V| – |E| + k = 2 n=9 m=15 k=8 9 – 15 + 8 = 2 Гомеоморфизм графов n Два графа гомеоморфны, если они получаемы из одного и того же графа операцией добавления вершины в ребро n Любые циклические графы гомеоморфны n Гомеоморфизм является отношением эквивалентности Критерии планарности графов n Критерий Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда у него нет подграфов, гомеоморфных К5 или К3,3 n Критерий Вагнера (Харари-Татта). Граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к К5 или К3,3. Непланарный граф Петерсона Хроматические инварианты n Правильная раскраска вершин в æ цветов - это n n n n n разбиение V=V1 V2…Væ Наименьшее из æ при условии правильности раскраски называется хроматическим числом æ(G). Правильная раскраска ребер в  цветов - это разбиение множества ребер Е=Е1 Е2…. Е. Наименьшее из  при условии правильности раскраски называется хроматическим индексом (G). Раскраска, при которой окрашиваются и вершины, и ребра, а правильность означает принадлежность двух инцидентных элементов различным одноцветным классам, называется тотальной раскраской в  цветов. Наименьшее число цветов – тотальный минимум(G).