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


 

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

80675. Планирование культуры экономической организации 186.5 KB
  Планирование организационной культуры - вид планирования, в определенном смысле противоположный процессу и результатам финансового планирования. Если финансовое планирование имеет дело с предельно точными, конкретными величинами, то планирование культуры связано с наименее определенным, слабо контролируемым элементом внутрифирменной среды. Основу культуры составляют человек, его поведение
80680. Экономико-статистическое прогнозирование 42 KB
  Методы различаются также по научной обоснованности и назначению. В большом многообразии методов многообразия можно выделить следующие их группы: методы экспертных оценок; методы экстраполяции; моделирование; нормативный метод; целевой метод. Методы экспертных оценок основан на использовании экспертной информации. Методы экстраполяции основываются на предположении о неизменности факторов определяющих развитие изучаемого объекта и заключается в распространении закономерностей развития объекта в прошлом на его будущее.
80681. Методы прогнозной экстраполяции 63 KB
  Цель такого прогноза показать к каким результатам можно прийти в будущем если двигаться к нему с той же скоростью или ускорением что и в прошлом. Прогноз определяет ожидаемые варианты экономического развития исходя из гипотезы что основные факторы и тенденции прошлого периода сохраняться на период прогноза или что можно обосновать и учесть направление их изменений. Для данной цели необходимо чтобы прогностическая модель имела достаточную точность или допустимо малую ошибку прогноза. Ошибка статистического прогноза будет меньше чем...
80682. АНАЛИЗ КАЧЕСТВА ПРОГНОЗОВ 54.5 KB
  Абсолютная ошибка прогноза которая может быть определена как разность между фактическим значением и прогнозом Среднее абсолютное значение ошибки: 3. Среднеквадратичная ошибка прогноза: Между средним абсолютным значением ошибки и существует связь. Поэтому абсолютная ошибка прогноза может быть выражена в относительно фактических значений показателя: А средняя относительная ошибка: Этот показатель используется при сравнении точности прогнозов разнородных объектов прогнозирования поскольку этот показатель характеризует относительную...