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


 

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

5289. Общие понятия об устойчивости работы объектов экономики и жизнеобеспечения населения 167 KB
  Общие понятия об устойчивости работы объектов экономики и жизнеобеспечения населения. Факторы, влияющие на устойчивость этих объектов УЧЕБНЫЕ ЦЕЛИ: Довести до слушателей содержание, организацию подготовки отраслей и объектов к устойчивому функцио...
5290. Действия руководителей формирований ГО и РСЧС при организации и проведению АСДНР 109.5 KB
  Действия руководителей формирований ГО и РСЧС при организации и проведению АСДНР УЧЕБНЫЕ ЦЕЛИ: Совершенствовать знания и навыки руководителей формирований ГО и РСЧС по организации и проведению АСДНР. ВРЕМЯ...
5291. Защита населения путем эвакуации при чрезвычайных ситуациях 114 KB
  Защита населения путем эвакуации при чрезвычайных ситуациях 1 Изучить с требования руководящих документов по организации, планированию и проведению эвакуационных мероприятий в чрезвычайных ситуациях мирного и военного времени. Изучить виды о...
5292. Воздействие поражающих факторов ядерного оружия, обычных средств поражения и основных АХОВ на население и объекты 1.4 MB
  Изучить характеристику очага ядерного поражения. Изучить характеристику очагов поражения обычных средств поражения. Ознакомить с воздействием токсичных свойств основных АХОВ на население Место проведения занятия: класс инженерной защиты...
5293. Прогнозирование и оценка инженерной обстановки в интересах подготовки к защите и по защите населения, материальных и культурных ценностей 715 KB
  Изучить сущность прогнозирования обстановки в интересах защиты населения и территорий. Изучить метод прогнозирование инженерной обстановки на территории города при воздействии ядерных средств поражения. Ознакомить с методом прогнозирование...
5294. Организация строительного производства. Проектирование строительных. Генеральных планов 438.5 KB
  Введение Настоящие методические указания определяют состав, содержание, объем, последовательность и методику проектирования строительного генерального плана в курсовом и дипломном проектах по организации строительства. Предлагаемые методические указ...
5295. Эпоха Петра Великого 81 KB
  Задание №1 Что означают эти понятия. Адмиралтейство, ассамблеи, Берг-коллегия, великое посольство, всешутейший и всепьянейший собор, Генерал-прокурор, генералиссимус, Генеральный регламент, Главный магистрат, гражданская азбука, князь-кесарь...
5296. Комплексная оценка основных показателей качества бензина 310.88 KB
  Комплексная оценка основных показателей качества бензина. Цель работы, изучение технических норм на бензин, методик и приборов, выполнение испытания по определению плотности, фракционного состава, наличия водорастворимых кислот и щелочей, октанового...
5297. Машины для укладки рельсошпальной решетки 2.52 MB
  Введение Данная курсовая работа посвящена изучению путевых машин и механизированных комплексов выполняющих различные работы в путевом хозяйстве. Тема работы - машины для укладки рельсошпальной решётки. Целью работы является подробное изучение к...