Планарность. Обходы графов

Планарность Граф называется планарным, если изоморфен плоской геометрической интерпретации грани графа - внутренние, внешняя эйлерова характеристика графа  G   n  m  k Теорема. Для любого планарного связного графа  G   2 Доказательство. Т – остов графа G  (T )  n  (n  1)  1  2 V (T )  V (G)  n Т – дерево  (G)  n  (n  1  (G))  1  (G)  2 m  3n  6 Следствие 1. Для любого связного планарного графа n  3 Доказательство. P  ( F , e) | e ребро грани F Рассмотрим Докажем 3k  2m 3k  P  2m  G   n  m  k  2 m  3n  6 3m  n  2  2m k  mn2 Следствие 2. Граф К5 – не планарный Следствие 3. Граф К3,3 – не планарный m  10 m9 n5 n6 10  3  5  6  9 10  3  6  6  12 Допустим, что К3,3 планарный граф   K3,3   6  9  k  2  k  5 Для К3,3 справедливо 4k  2m  4  5  2  9 - противоречие Графы G и G называются гомеоморфными, если существуют такие их подразделения, которое изоморфны G Теорема Куратовского-Понтрягина. (Критерий плоской реализуемости). Граф G(V,E) планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К5 и К3,3. G Задача о трех домах и трех колодцах (Куратовский 1930 г.) Число планарности – минимальное число ребер, которые необходимо удалить для получения плоского изображения Толщина графа – минимальное число плоскостей, необходимых для геометрической реализации K3,3 - не планарный Обходы графов Задача о Кенигсбергских мостах C А D B Эйлер в 1736г. Цикл называется эйлеровым, если каждое ребро графа участвует в его образовании один раз. Граф, содержащий такой цикл, называется эйлеровым Теорема. Связный неориентированный мультиграф G(V,E) тогда и только тогда является Эйлеровым, когда степень каждой из его вершин – четное число. Доказательство. 1) граф содержит эйлеров цикл тогда для каждой вершины справедливо: каждому входящему ребру соответстветствует выходящее, следовательно, степень каждой вершины четна C А D B 2) степень каждой вершины – четное число Рассмотрим граф G1  G / C1 Рассмотрим вершину ai граф связен  (ai , a j ) Повторим процесс С2  G / C1 … deg a j - четная  (a j , ak ) G  C1  C 2  ...  C n … Процесс закончится возвращением в ai Получили цикл С1  G Алгоритм построения эйлерова цикла (Флёри) 1) Проверяем эйлеровость по теореме. 2) Выбираем произвольную вершину ai , произвольному ребру, ей инцидентному присваиваем номер 1, считая его пройденным (пройденные ребра удаляются) 3) Находясь в очередной вершине выбираем не пройденное ребро (выбираем ребро, являющееся мостом и инцидентное вершине ai , только при отсутствии других вариантов) 1 3 2 5 4 7 8 6 9 1 2 3 4 5 6 7 8 9 2 1 4 3 4 5 2 1 2 6 2 4 5 6 7 8 6 8 3 4 5 5 8 6 8 7 9 9 обход вершин – методом поиска в глубину 1 2 3 6 5 2 4 5 8 6 9 8 7 41 Цепь называется эйлеровой, если каждое ребро графа участвует в её образовании один раз. Граф, содержащий такую цепь, называется полуэйлеровым Теорема. Связный неориентированный мультиграф G(V,E) тогда и только тогда является полуэйлеровым, когда существуют точно две вершины нечетной степени. Теорема. Орграф является эйлеровым тогда и только тогда когда для всех вершин deg  a  deg  a Орграф является полуэйлеровым, тогда и только тогда когда для всех вершин deg  a  deg  a кроме двух, для которых выполняются deg  a  deg  a  1   для одной и deg a  1  deg a для другой. Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа ровно один раз. Граф, содержащий такой цикл, называется гамильтоновым. Если такой простой путь не является циклом, то граф называется полугамильтоновым. Достаточные условия существования гамильтоновых циклов: 1. Если для любых двух различных несмежных вершин a и b графа G(V,E) выполняется условие deg a  deg b  n, то существует гамильтонов цикл. n 2. Если для любой вершины a графа G(V,E) выполнено условие deg a  , 2 то существует гамильтонов цикл (условие Дирака) Задача коммивояжера 1. Сеть коммуникаций. 2. Просверливание отверстий программируемым станком. Дан G(V(n),E(m)) – реберно-взвешенный граф с матрицей весов   w12 w  21  W (G )  ...  ...   wn1 wn 2 ... w1n  ... w2n   ... ...   ...   1 шаг. wi*  min wi1, wi 2 ,...win  i  1,2,...,n    w21  w2* *  W (G )   ...   wn1  wn* ... w1n  w1*  *  ... w2n  w2  ... ... ...   * wn 2  wn ...   w12  w1* *   w12  w2**  * ** w  w  ** * *  21 1 wi  min w1i , w2i ,...wni  i  1,2,...,n W (G )   ... ...  *  wn1  w1** wn* 2  w2** X – гамильтонов цикл W ( X )  h  w1*  w2*  ...  wn*  w1**  w2**  ...  wn** ... wn*1  wn**  * **  ... wn 2  wn   ... ...  ...   2 шаг. a1, a2 ,...,as b1, b2 ,...,bt  - множество гамильтоновых циклов, в которых первыми вершинами являются a1, a2 ,...,as , а вершина as 1  b1, b2 ,...,bt  h w1k1  w1* 3 шаг. (для подзадачи   wk*1*2  h2  h  h h1  h  h **  w21   1, k1 O  1k1 ...  ... ** ** hi  min h1, h2  W G   wk1 11 wk1 12   wk*1*11 wk*1*12 …  ...  ... **  wn**1 w n 2  4 шаг. (для подзадачи 1k1) … 1, k1 O ) ... wk*1*k1 1 wk*1*k1 1 ... ... w2**k1 1 w2**k1 1 ... ... ... ...  ... ... wk*1*1k1 1 ... ... ... ** wnk 1 1 ... wk*1*1k1 1 ...  ... ... ... ** wnk 1 1 ... wk*1*n   **  w2n  ...  wk*1*1n   ** wk1 1n   ...    W   W ** ( w1*k*1  ) Замечание. Если решение отсутствует, то в итоге нижняя граница получится равной  Гамильтонов цикл с максимальным весом   wmax  max wij  W  wij  wmax  wij  1 2 3 4 5 6 1  13 7 5 2 9 2 8  4 7 5  W 3 4 8 5 4 8  3 1  6 2 1 5  6 1 4  9 6 10 8 3 7  1 2 3 4 5 6 1  11 5 2 7 2  2 1  W **  3 2 1 2 8  0 1  4 1 5  5 2  8 6 8 2 7  4 6 1 w1*  2 w2*  4 w3*  2 w4*  0 w5*  1 w6*  0 2 3 4 5 6 1  11 5 3 7 2 4  3 1  W*  3 4 6 5 2 8  1 1  4 1 5  5 3  8 w5**  0 6 10 8 3 7  w6**  0 W **  2 3 4 6 x  5 2 8 2  2  3 2 2  4 7  6 6 8 2  w2**  0 w3**  0 w4**  1 h  2  4  2  0  1  0  4  0  0  1  0  0  14 14 15 16 1,5O  W  15 x 2 3 4 6 x  5 2 8 2  2  3 2 2  4 1 8 1  1 6 6 8 2  1 x w1**  4 1,5,3O  h  1 1,53 h  2 2 3 4 5 6 1  11 5 2  7 2  2 1  W   3 2 1 2 8  0 1  4 1 5  5 2  8 6 8 2 7  4 6 14 W **  15 16 1,5O  15 15 17 1,5,3O  x 1,53 17 W   6 W **  W  1,5,3,4O  1,5,34 15 4 2 3 4 6 x  5 2 8 2  2  3 2 2  4 7  6 6 8 2  6 x  2 0 0 W  2 0  2  4 0 7  0 6 15 2 x h  0 1,5,3,4,6O  1,5,3,46 x 2 6 x  7 2   6 6 2 2  h  0  2 2 3 4 6 x  5  2 8 2  2  3 2 2  4 7  6 6 8 2  h  2 h  0 x W  x  W   x W  x 2 4 6 x  2  0 W   2 0  2  4 0 7  0  h  2 6 6 x 2 6 x  7  2   h   6 6  2  Гамильтонов цикл минимального веса 15 (1,5,3,4,6,2,1)