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


 

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

39531. Информационные технологии. Формы и способы представления данных 1.02 MB
  Формы и способы представления данных. Информация это интерпретация данных. 2 способа представления данных: в текстовом и числовом виде Текстовые данные воспринимаются передающими системами как текст записанный на какомлибо языке. Информационная технология это система методов и способов сбора накопления хранения поиска обработки анализа выдачи данных информации и знаний на основе применения аппаратных и программных средств в соответствии с требованиями предъявляемыми пользователями.
39532. Математическое моделирование 282.2 KB
  Для оценки эффективности проекта срок окупаемости с учетом дисконтирования следует сопоставлять со сроком реализации проекта длительностью расчетного периода. Норма дисконта определяется каждым участником проекта самостоятельно. Для эффективности проекта необходимо чтобы его ЧДД был положительным. Если ЧДД = 0 то проект находится на грани между эффективным и неэффективным что требует не отказа от проекта а более внимательного рассмотрения исходных данных заложенных в расчет эффективности.
39533. Приборы СВЧ и оптического диапазона 184 KB
  Требуется определить как надо изменить другой параметр чтобы получить ту же выходную мощность или как при этом изменится режим усилителя. Во сколько раз надо изменить мощность возбуждения чтобы выходная мощность осталась неизменной Решение: см. найдём отношение: Поскольку сначала до изменения параметров клистрон работал в оптимальном режиме то по графику определяем : Электронная мощность изменяется при изменении тока и напряжения . Но параметры не изменяются при условиях задачи а мощность возбуждения значит результат...
39534. Аудит показателей бухгалтерского баланса в соответствии с МСФО 451.5 KB
  Трудности возникают и из-за несовпадения временных периодов, а также методики учета по окончании периода. Это связано с тем, что и в той и другой системах предусмотрено применение различных отчетных периодов, различных способов закрытия счета и т. д. При этом приходится закрывать счета в каждой базе данных.
39535. Математическое программирование (ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ) 2.42 MB
  Различные формы модели задачи линейного программирования . Формулировка основной задачи линейного программирования . Понятие допустимого решения области допустимых решений оптимального решения задачи линейного программирования . Переход от задачи минимизации целевой функции к задаче максимизации .
39536. Двухэтажный жилой дом с гаражом 212.13 KB
  Условия организации и осуществления строительства Жилое двухэтажное здание с гаражом находится в районе города Луганск который относится к 1 климатическому району.56 Кладка внутренних стен при высоте этажа до 4 м.03 V=FF Кладка перегородок толщиной в 1:2 кирпича при высоте этажа до 4 м.
39537. Экстраполяция трендов. Модель спрос-предложение 86.28 KB
  Постановочный этап: определяются конечные цели исследования моделирования набор участвующих в модели факторов и показателей и их роли. 3 Этап параметризации и спецификации модели: собственно моделирование то есть выбор вида модели функции регрессии в том числе состава и формы входящих в нее связей между переменными. 5 Этап идентификации модели: статистическое оценивание неизвестных параметров модели по собранным данным статистический анализ модели. 6 Этап верификации модели: сопоставление фактических реальных данных и...
39538. РАЗРАБОТКА ПРОГРАММЫ РАСПРЕДЕЛЕНИЯ ДОКУМЕНТООБОРОТА В МНОГОПРОФИЛЬНОМ ОАО 1.47 MB
  Делопроизводство - это термин, используемый в конторской практике для набора правил работы с документами. Есть системы документооборота, которые настраиваются на правила делопроизводства. Есть системы, которые изначально ставят своей целью выполнение именно этих правил и содержат более общие функции в достаточной мере, чтобы их назвали системами документооборота.
39539. Разработка мероприятий по повышению финансовых результатов деятельности ООО «ПАРИТЕТ ПЛЮС» 641.96 KB
  Об абстрактности и конкретности философии государства и права. Попытки создать философию права как некую универсальную и всеобщую конструкцию исходящую из каких бы то ни было оснований антропологического материализма объективного или субъективного идеализма экзистенциализма или позитивизма на протяжении более чем двух столетий в Европе и России оказались несостоятельными. Оказалась не более чем иллюзией и сознательно разработанным мифом попытка представить право и полный свод правильных законов как способ решить все основные задачи по...