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


 

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

67535. УПРАВЛЕНИЕ ОТХОДАМИ 832 KB
  Накопление отходов в окружающей среде и вызываемое ими вторичное загрязнение в результате длительного хранения наряду с задолживанием территорий развитием экспорта отходов в пространстве и времени делают приоритетными вопросы эффективного обращения с отходами и снижение эмиссии в окружающую среду.
67536. Амплитудное и фазовое управление двухфазным асинхронным двигателем с полым ротором. Следящий электропривод переменного тока с сельсинами 229 KB
  Одна из фаз называется обмоткой возбуждения а другая – обмоткой управления. Если на обмотки возбуждения и управления подать напряжения сдвинутые по фазе на угол π 2 например то получается магнитное поле вращающееся с синхронной частотой ω1. При уменьшении напряжения управления магнитное...
67537. МЕХАНИЧЕСКАЯ ЧАСТЬ СИЛОВОГО КАНАЛА ЭЛЕКТРОПРИВОДА 300.5 KB
  На рис. 13.3 показана тележка, на которую действует сжатая пружина с силой F = cx, где с – коэффициент жесткости пружины; x – величина ее деформации. Сила направлена вправо независимо от направления движения – влево или вправо. Действие пружины обусловлено ее потенциальной энергией упругой деформации.
67538. Функции передаточного устройства. Характеристики агрегата «двигатель-редуктор». Выбор мощности двигателя по типовому движению 213 KB
  Третьей функцией передаточного устройства является изменение скорости вращения и момента для согласования характеристик двигателя и исполнительного механизма. Масса объем мощность потерь и стоимость электродвигателя определяются его моментом М2 а мощность на валу дается формулой P2 = M2 ω.
67539. Электропривод с упругими связями. Уравнения трехмассовой системы и колебания в двухмассовой системе. Люфт в механической передаче. Удары и выход из контакта. Механическая передача с упругими связями 247.5 KB
  Рассмотрим упругий стержень, к концам которого приложены моменты М1, М2 (см. рис. 15.1). Концы имеют углы поворота α1 и α2, коэффициент жесткости стержня с12 . Если не учитывать момент инерции стержня, то из условия равновесия моментов получаем равенства...
67540. Установившиеся и переходные процессы в электроприводах. Система уравнений динамики двигателя постоянного тока независимого возбуждения 72.5 KB
  Система уравнений динамики двигателя постоянного тока независимого возбуждения Переходные процессы в электрических приводах. Примеры установившихся процессов для тока На рис.1 приведены примеры установившихся процессов для электрического тока постоянный ток переменный синусоидальный...
67541. Электромеханический и электромагнитный переходные процессы в двигателе постоянного тока независимого возбуждения. Электромеханический переходной процесс 140.5 KB
  Через время Тэм экспонента уменьшается в е = 2,71828 раз. За время 2Тэм она уменьшится в е2 раз. Через время 3Тэм экспонента уменьшается приближенно в 20 раз, тогда считают, что переходной процесс заканчивается (остается 5 % от первоначального значения экспоненты).
67542. Совместное протекание электромагнитного и электромеханического переходных процессов в двигателе постоянного тока независимого возбуждения 163 KB
  Апериодический и колебательный процессы Совместное протекание электромагнитного и электромеханического переходных процессов в двигателе постоянного тока независимого возбуждения. Допустим что в двигателе постоянного тока независимого возбуждения uв = const; Ф = const но индуктивность якоря...
67543. Метод последовательных интервалов. Включение обмотки возбуждения. Пуск двигателя постоянного тока последовательного возбуждения и трехфазного асинхронного двигателя. Метод последовательных интервалов 143 KB
  Для решения нелинейных дифференциальных уравнений на ЭВМ в настоящее время применяются эффективные численные методы. Включение обмотки возбуждения Рассмотрим переходный процесс при включения обмотки возбуждения двигателя постоянного тока на постоянное напряжение.