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


 

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

37362. Выдача иностранным гражданам и лицам без гражданства вида на жительство в РФ 48 KB
  Вид на жительство — документ, выданный иностранному гражданину в подтверждение его права на постоянное проживание в Российской Федерации, а также его права на свободный выезд из Российской Федерации и въезд в Российскую Федерацию. Вид на жительство, выданный лицу без гражданства, является одновременно и документом, удостоверяющим его личность.
37363. Разработка программного обеспечения решения задачи о назначении сотрудников на должности 199.52 KB
  Имеется конечное число видов работ, которые могут быть выполнены потенциальными кандидатами на эти должности. При этом каждого кандидата можно назначить на выполнение только одной работы, а каждая работа, в свою очередь, должна выполняться только одним кандидатом. Известна эффективность выполнения каждой работы (или издержки при назначении) любым из потенциальных кандидатов.
37364. ОБОРУДОВАНИЕ УЧАСТКА ЖЕЛЕЗНОЙ ДОРОГИ СИСТЕМОЙ АВТОБЛОКИРОВКИ С ТОНАЛЬНЫМИ РЕЛЬСОВЫМИ ЦЕПЯМИ И ЦЕНТРАЛЬНЫМ РАЗМЕЩЕНИЕМ ОБОРУДОВАНИЯ ТИПА АБТЦ-03 60.02 KB
  Для управления и правильного пользования сигналами раздельные пункты станции ограничивающие перегон оборудуют блокировочными аппаратами и релейными приборами и связывают их электрически между собой двухпроводной линейной цепью. От этого сигнала срабатывает релейная аппаратура ПАБ которая обеспечивает зависимость по управлению светофором. На железных дорогах используются в основном релейные системы ПАБ Гипротранссигналсвязи РПБ ГТСС. В релейных системах все блокировочные зависимости и необходимые замыкания осуществляются с помощью реле...
37365. Оборудование промежуточных станций электрической централизацией стрелок и сигналов 57.23 KB
  Задача курсового проекта заключается в разработке системы электрической централизации по заданному плану станции для данной горловины. В курсовом проекте используется блочная маршрутно-релейная централизация, так как она обеспечивает маршрутное управление, что обеспечивает сокращение времени на установку маршрута и так же позволяет повысить производительность труда.
37366. Строительство здания на основе проэкта Доступное и комфортное жилье — гражданам России 83 KB
  Наша область одна из первых в России начала формировать систему градостроительной деятельности соединяющую электронные топографические карты со справочной аналитической и другой информацией для создания топографической основы территорий.1 Объемнопланировочное решение здания. Общая высота здания 72м.2 Конструктивное решение здания.
37367. Расчет грузового барабана лебедки 2.83 MB
  Определение коэффициентов относительной ширины колес Для несимметричного расположения колес относительно опор коэффициенты относительной ширины колес для тихоходной и быстроходной ступеней при твердости ≥350 НВ назначаются из интервала [1 табл. Расчет эквивалентного времени работы Эквивалентное время работы Lhe назначают с учетом категории режима работы по ГОСТ 2135487 и находится по формуле: Lhe = h Lh где Lh заданный срок службы час; h коэффициент эквивалентности зависящий от режима нагрузки. Геометрические расчеты...
37368. Проектирование привода к вертикальному валу цепного конвейера 13.07 MB
  Повышение эксплуатационных и качественных показателей, сокращение времени разработки и внедрения новых машин, повышение их надежности и долговечности - основные задачи конструкторов-машиностроителей. Одним из направлений решения этих задач является совершенствование конструкторской подготовки студентов высших технических учебных заведений.