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


 

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

32711. Противосудорожные средства 107 KB
  Противосудорожные средства ПСС лекарственные вещества угнетающие двигательные центры ЦНС и применяемые при различных судорожных состояниях а также для лечения спастичности и паркинсонизма. ПРОТИВОСУДОРОЖНЫЕ СРЕДСТВА Для купирования Средства для лечения симптоматических судорог болезни Паркинсона Средство для лечения...
32712. Тема вина в творчестве Мо Яня на материале произведений «Страна вина», «Вверх ногами» 141.5 KB
  Произвести обзор творчества писателя в целом. Выявить основные литературные приемы писателя. Рассмотреть отношение китайского общества к употреблению алкоголя. Выявить позицию автора к проблеме алкоголизма в Китае через использование писателем темы вина в произведениях «Страна вина» и «Вверх ногами».
32713. ПРОБЛЕМЫ ЭКОЛГИЗАЦИИ ТЕХНОЛОГИИ В НЕФТЕПЕРЕРАБОТКЕ 104 KB
  Вначале человек не задумывался о том, что таит в себе интенсивная добыча нефти и газа. Главным было выкачать их как можно больше. Так и поступали. Но вот в начале 40-х гг. текущего столетия появились первые настораживающие симптомы.
32714. ПРОБЛЕМЫ ОБЕСПЕЧЕНИЯ БАНКОВСКИХ КРЕДИТОВ И ПУТИ РАЗВИТИЯ ФОРМ ВОЗВРАТНОСТИ КРЕДИТА 670.5 KB
  Рассмотреть наиболее часто используемые формы обеспечения возвратности кредитов: залог, уступка требований (цессия) и передача права собственности, гарантии и поручительства и др.; на примере ОАО «Сбербанк» получить представление о возможностях банка по возврату кредитов.
32715. ЭКОНОМЕТРИЧЕСКИЕ ИССЛЕДОВАНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ПАССАЖИРООБОРОТА ЖЕЛЕЗНОДОРОЖНЫХ ПЕРЕВОЗОК ОТ ДЛИНЫ ДОРОГИ 336 KB
  В конце прошлого столетия разработаны и широко применяется для решения большого числа практических задач экономики математические модели, в основу которых положены уравнения регрессии. В настоящей курсовой работе стоит задача обосновать математическую модель пассажирооборота железнодорожных перевозок
32716. Сердечные гликозиды, Механизм кардиотонического действия 94 KB
  Сердечные гликозиды вещества растительного происхождения которые оказывают высокоизбирательное кардиотоническое действие. Исследования зависимости между структурой и действием этих средств показали что лактонное кольцо и стероидное ядро в равной мере необходимы для проявления активности. Действие на сердце. Систолическое действие инотропное Усиление и укорочение систолы.
32717. АНТИАРИТМИЧЕСКИЕ СРЕДСТВА 123 KB
  Антиаритмический эффект проявляют так же вещества действие которых направлено на эфферентную иннервацию сердца. Поэтому в механизме действия ААС ведущую роль играет их действие на клеточные мембраны транспорт ионов N K C и взаимосвязанные с этим изменения мембранного потенциала кардиомиоцитов. Препараты могут угнетать сократимость обладать умеренным Мхолинолитическим действием устранение влияния вагуса может способствовать распространению предсердной аритмии на желудочки. Влияет на все отделы проводящей системы сердца угнетает...
32718. АНТИАНГИНАЛЬНЫЕ СРЕДСТВА 118.5 KB
  ngin pectoris грудная жаба лекарственные средства применяемые для купирования и предупреждения приступов стенокардии и лечения других проявлений коронарной недостаточности при ишемической болезни сердца включая безболевую форму. При всех видах стенокардии возникает несоответствие между кровоснабжением миокарда и его потребностью в кислороде. Средства понижающие потребность миокарда в кислороде и повышающие доставку кислорода а нитраты Препараты нитроглицерина Для применения в медицинской практике нитроглицерин выпускают в виде готовых...
32719. ЛЕКАРСТВЕННЫЕ СРЕДСТВА ДЛЯ ЛЕЧЕНИЯ АТЕРОСКЛЕРОЗА (ГИПОЛИПИДЕМИЧЕСКИЕ СРЕДСТВА) 105.5 KB
  Ведущая роль отводится высокому содержанию холестерина в липопротеинах низкой плотности участвующих в образовании дестабилизации атеросклеротических бляшек и тромбогенезе. Цель их использования заключается в понижении концентрации в крови атерогенных липопротеидов липопротеидов низкой плотности ЛПНП липопротеидов очень низкой плотности ЛПОНП и холестерина ХС а также повышении концентрации антиатерогенных липопротеидов высокой плотности ЛПВП. Лекарственные средства как правило имеют несколько механизмов действия один из которых...