67604

Планарность и раскраска графов

Лекция

Математика и математический анализ

Такая функция называется плоским мультиграфом. Внутренние грани плоского мультиграфа называется конечная плоскость окруженная простым циклом и не содержащая внутри себя никаких ребер. Называется её границей.

Русский

2014-09-12

97.5 KB

2 чел.

Лекция №15

Планарность и раскраска графов

опр || мультиграф называется планарным если его можно нарисовать на плоскости так, что  2 дуги (ребра) либо не имеют общих точек, либо имеют общие точки, совпадающие с вершинами графа.

В  точках пересечения сходятся лишь дуги инцидентные вершине, совпадаюшей с точками пересечения.

Такая функция называется плоским мультиграфом.

Внутренние грани плоского мультиграфа называется конечная плоскость окруженная простым циклом и не содержащая внутри себя никаких ребер.

Простой цикл ограничен. Называется её границей.

Часть плоскости состоящая из точек принадлежащих графу и какой либо её плоскости называется её высшей степенью.

Для связанных плоских мультиграфов выполняется соотношение Эйлера

n – количество вершн

m – количество ребер

- гр. внеш

Критерий планарности

Теорема Плантрагина-Куратовского

Теорема || Граф планарен тогда и только тогда, когда ни одна из его подграфов не гомопотрофна следующим графам

        

Раскраской вершин графа (или ребер мультиграфа) называется сопоставление вершинам определенных цветов.

Раскраска называется правильной если смежные вершины (ребра) окрашены в разные цвета.

Наименьшее число цветов для каждого  прав. раскраски графа G называется хроматическим числом и обозначается X(G)

1)

2)

3)

Для хроматического индекса свойства:

1)

2) G граф

Транспортные сети

Транспортной сетью называется орт граф

для которого выражаются условия:

1)  одна и только одна вершина называется источником

множество дуг заходящих в точку

2)  -//- верш .  называется истоком т.ч.

3) Каждой дуге  сопоставляется число (целое и не отрицательное) т.ч.  называемое пропускной способностью дуги

4) Вершины отличные от источника и истока называются промежуточными

опр || потока

Функция  определенная на множестве X граф D и принимающая целочисленные значения называется потоком транспортной сети D, если

1) для  дуги

2) для  промежуточной дуги x

2,5) для  промежуточной вершины

Сколько вышло столько и вошло.

опр ||  называется насыщенным, если поток по ней равен ее пропускной способности

опр || поток  называется полным, если его путь из  в  содержит хотя бы одну насыщенную дугу

опр || Поток называется максимальным, если   принимает максимальное значение по сравнению с другим допустимым потоком.

Замечан || максимальный поток является полным, но обратно не верно.

Алгоритм построения полного потока

1)

2) из  удаляем дуги являющиеся насыщенными

3) ищем в  простую цепь

, если не находим, то конец.

- искомый поток по определению

4) Увеличим поток по всем дугам на одинаковую величину т.ч. хотя бы одна дуга из  является насыщенной, потоки по остальным не превышают их пропускных способностей


 

А также другие работы, которые могут Вас заинтересовать

15126. Ахмет Байтұрсынұлының өмірі мен қызметі 47 KB
  А. Байтұрсыновтың өмірі мен қызметі Кезінде репрессияға ұшырап мерт болған боздақтар қайта тірілді сөнген жанып жоғалған табылды. Алыптар қайта оралды. Тұтас буынның төлбасы кешегі Абай Ыбырай Шоқан салған ағартушылық демократтық бағытты ілгері жалғастырушы ір...
15127. Б. Адамбаев - фольклортанушы 37.5 KB
  ӘОК 8219 Қ64 Б. АДАМБАЕВ ФОЛЬКЛОРТАНУШЫ М.Б. Қоңқашова ӘулиеАта университеті Тараз қ. Қазақ ауыз әдебиеті туралы ғылыми зерттеулер он тоғызыншы ғасырда өз бастауын алды. Бұған дейінгі уақытта қазақ фольклоры жайында жекелеген пікірлер ғана айтылып т
15128. Баймырзаұлы Балуан Шолақ 41.5 KB
  Баймырзаұлы Балуан Шолақ 1864-1916 – қазақтың халық композиторы ат ойынының түрлі тәсілін меңгерген өнерпазы күш өнерін көрсеткен спортшысы жауырыны жерге тимеген балуаны. Оның есімін де халық осы соңғы өнеріне сүйсінгендіктен еркелет
15129. Балалардың сүйікті жыршысы - Мұзафар Әлімбай 320 KB
  Балалардың сүйікті жыршысы М.Әлімбаевтың шығармашылығына арналған әдістемелік құрал Ол алуан қырлы талантты ақын Д.Әбілов Кіріспе орнына Қымбатты достым қалай ойлайсыз қазіргі қазақ әдебиеті мен поэ
15130. Батыр жырау - Қожаберген 173.5 KB
  Ел тарихын ұмыттырмаған ән €œҚожаберген жыраудың шығармаларын сұрыптап толықтырылған жинағын баспаға дайындап жатыр едiк соған сiз алғы соз жазсаңыз€ деп Қызылжардан телефон шалғанда уәдемдi берiп қалып едiм. Өзiң атқарар iстi бiреу жарқыратып атқарып жатса құдайды...
15131. Бейімбет Майлин 89.5 KB
  Бейімбет Майлин Майлин Бейімбет 1894-1938 Бейімбет – поэзия проза драма саласында бірдей өнімді еңбек еткен қаламгер. Ол Садақ қолжазба журналында Айқап журналында Қазақ газетінде жарияланған алғашқы өлеңдерінен бастапақ ел өмірінің сансала көкейкесті мәсе...
15132. Бұқар жырау Қалқаманұлы 39.5 KB
  Қалқаманұлы Бұқар жырау Қалқаманұлы Бұқар жырау 1668 1781 қазақтың ұлы жырауы 18 ғ. жоңғар басқыншыларына қарсы қазақтың азаттық соғысын бастаушысы әрі ұйымдастырушысы атақты Абылай ханның ақылшысы. Шыққан тегі Арғын тайпасының қаржас руынан. Заманындағы сыншылар о
15133. Ғабиден Мұстафин 104.5 KB
  ҒАБИДЕН МҰСТАФИН 1902-1985 Мен әрдайым бүгінгіні шамам келгенше – ертеңгіні жаздым. Жазушы алдымен өз дәуірінің жаршысы. Мен өз бойымдағы бүкіл дарыным мен күшқуатымды халық мүддесіне қалтқысыз алаңсыз бағыштаған жазушымын. Менің творчествомның өзегі а...
15134. Ғабит Мүсірепов 55.5 KB
  ҒАБИТ МҮСІРЕПОВ 1902-1985 Қазақ әдебиетінің кеңестік дәуірдегі көрнекті қайраткерлерінің бірі көркемсөз зергері Ғабит Махмұтұлы Мүсірепов 1902 жылы қазіргі Солтүстік Қазақстан облысының Жамбыл ауданында кедей шаруаның отбасында дүниеге келген. Ол алғаш өз а