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) Увеличим поток по всем дугам на одинаковую величину т.ч. хотя бы одна дуга из  является насыщенной, потоки по остальным не превышают их пропускных способностей


 

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

19589. Християнство як світова релігія. Новітні релігійні течії 90 KB
  Християнство виникло у 2-й половині 1 століття н.е. у східних провінціях Римської імперії в умовах розпаду рабовласницького ладу. Віросповідними джерелами християнства є «святе письмо» (Біблія) і «священний переказ» - постанови Вселенських соборів, деякі напрямки християнства визнають і інші джерела своєї догматики
19590. Индикаторные приборы 321.67 KB
  При высоковольтной катодолюминесценции электроны ускоряются большими напряжениями (кВ — десятки кВ) и при бомбардировке люминофора проникают почти на всю его глубину. При этом выбиваются вторичные электроны, которые летят к ближайшим положительно заряженным электродам
19591. Методи проектування (фантазування, елементи біоніки). Вибір об’єкту проектування на основі зібраної інформації. Складання ескізу майбутнього виробу 48.5 KB
  Тема уроку: Методи проектування фантазування елементи біоніки. Вибір обєкту проектування на основі зібраної інформації. Складання ескізу майбутнього виробу. Мета: сформувати уявлення про художньоконструкторську діяльність процес проектування та його основні
19592. ПЛАСТИЧНІ МАСИ 45 KB
  Пластичні маси (пластмаси) — матеріали на основі природних або синтетичних полімерів, здатні під впливом нагрівання і тиску формуватися у вироби складної конфігурації. Обовязковим компонентом усіх пластмас, крім полімерів {органічних сполук
19593. Перспективи вдосконалення технологій міжнародного маркетингу на ринку шоу-бізнесу 199.68 KB
  Ринок послуг є різновидом товарного ринку і разом з цим, має ряд специфічних рис, що зумовлює особливий підхід до підприємницької та маркетингової діяльності, покликаної забезпечити задоволення попиту на послуги.
19594. Методи проектування. Художнє конструювання виробів 51.5 KB
  Тема 1.2: Методи проектування. Художнє конструювання виробів. Мета: Навчальна: сформувати знання з даної теми. Виховна: виховувати в учнів культуру праці. Розвиваюча: розвивати у школярів спеціальні здібності сприяти розвитку технічного мислення. Об...
19595. Вивчення універсального осцилографу С1-73 2.29 MB
  Універсальний осцилограф, призначений для вивчення форм електронних сигналів в діапазоні частот 0 – 5 МГц шляхом візуального спостереження и вимірювання їх амплітуд у діапазоні 0,02 – 120 В, часових інтервалів від 0,4 10-6 до 0,5 с.
19596. Ручні інструменти для нанесення фарб та лаків 221 KB
  Ручні інструменти для нанесення фарб та лаків. Лакофарбові матеріали на підготовлену поверхню наносять вручну пензлями а механізовано розпиленням наливом зануренням та на вальцових верстатах. Для ручного нанесення фарб на поверхню деревини застосовують різном
19597. Вивчення вимірювальних генераторів 4.05 MB
  Генератор Г3-112 – джерело низькочастотних синусоїдальних та прямокутних сигналів. Діапазон частот: від 10 Гц до 10 МГц для синусоїдального сигналу та від 10 Гц до 1 МГц для меандру