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


 

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

63503. Философская антропология. Человек в природе, культуре и системе социальных связей 75 KB
  Напор трудностей не выдерживают пытаются спрятаться от жизни чтобы за них кто то их основные проблемы решал. Чацкий их хватает на занятия науками искусствами государственными делами они хорошо укорененные в жизни духовно аристократичны самостоятельны...
63504. Гносеология и эпистемология. Проблема истины и ее критериев. Познание и практика 99 KB
  Раздел философии в котором изучаются познавательные возможности человека называется гносеологией. В знаниях научных больше всего объективного: независимого от человека и человечества. Глаз человека видит хуже глаза орла зато видит больше.
63505. Философские аспекты понимания общества. Специфика социального познания 78 KB
  Философские аспекты понимания общества. Социальное строение жизни общества изучает прежде всего социология вопросы управления общественной жизнью политология хозяйственную деятельность в материальном производстве экономическая теория и т.
63506. Формационная и цивилизационная концепции общественного развития 76.5 KB
  Да и времени не оставили нам уже не только людьми созданные но и природой уготованные 21 веку глобальные проблемы вокруг решения которых надо скорее всему человечеству объединиться несмотря на все цивилизационные различия и групповые эгоистичные мечты амбициозных правителей.
63507. Онтология. Единство мира. Монистические и плюралистические концепции бытия 64.5 KB
  Монистические и плюралистические концепции бытия. Уже автор термина бытие Парменид в тезисе о тождестве бытия и мышления утверждал познаваемость мира человеческим мышлением. Вопрос о единстве мира всего бытия или изначальной множественности значит и невозможности...
63508. Проблемы происхождения, эволюции и сохранения жизни во Вселенной 75 KB
  Например и в мозге человека есть но особенно для навигации птицы и пчелы удачно используют магнетит залетающий на Землю с Марса. Материальное это понятие обозначающее объективное бытие телесных вещей их свойств и отношений а идеальное это субъективная реальность высшая форма опережающего отражения бытия вменяемого...
63509. Структура научного познания, его формы. Фундаментальные и прикладные знания 107.5 KB
  Деление условно рамки отдельной науки часто мешают решению проблем это надо учитывать при структурировании научной работы. По сферам использования науки делятся на фундаментальные и прикладные отраслевые: нефтепереработки геологоразведки авиастроения...
63511. Теория урока теоретического обучения 73 KB
  При коллективном обучении то что знает один то должны знать все и то что знают все должен знать один Функции коллективной формы обучения: Наличие у всех участников общей цели. а уроки производственного обучения.