Элементы комбинаторики. Правила умножения и сложения

Ребра, инцидентные  одной и той же паре вершин, называют параллельными или кратными. Граф, содержащий кратные ребра, именуется мультиграфом.

Граф называется конечным, если множество его элементов (вершин и ребер) конечно, и пустым, если множество вершин пусто.

Ребро, концевые вершины которого совпадают, называют петлей.

Граф, без петель и кратных ребер, называется полным если каждая из его вершин соединена ребром.

Степенью вершины  в неориентир графе называется колво  ребер, инцидентных этой вершине.

Графы отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Изоморфные графы  имеют одинаковое число вершин, ребер, степени соответствующих вершин равны. 
 

16. Способы задания  графов.

В общем виде «задать граф» означает: описать  множество его вершин и ребер, а также отношение инцидентности.

Способы задания  графа:

1. Графический

2. Перечислением  вершин и ребер.

3. Задание графа матрицей инцидентности. Строки матрицы характеризуют вершины графа, столбцы – ребра графа.

Для неориентир графа: 1 – если вершина и ребро  инцидентны, 0 – если не инциндентна.

Для ориентир - -1 если вершина является началом ребра, 1 – если концом ребра, 0 – не инциндентны, 2 – ребро – петля.

4. Задание графа матрицей смежности.

Матрица смежности  – это квадратная матрица размера  n*n, которая по горизонтали и по вертикали учитывает все вершины графа.

Матрица смежности  не ориентир графа симметрична относительно главной диагонали. И колво ребер графа равно сумме элементов матрица, распол выше главной диагонали.

5. Задание графа  матрицей весов.

Матрица весов - вариант матрицы смежности для  взвешенного графа, представляет собой  квадратную матрицу размером n  n (n - число вершин), (i,j)-й элемент которой равен весу ребра / дуги (v , v), если таковое имеется в графе; в противном случае (i,j)-й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи. 

17. Маршруты и  циклы. Связность.

Маршрутом называется последовательность вершин и ребер, в которой любые 2 соседних элемента инцидентны.

Если в простом  графе маршрут задан последовательностью  вершин , то вершины и называются концами маршрута.

Маршрут называется замкнутым, если . Незамкнутым - если

Маршрут, в котором  нет повторений ребер, называется цепью. Замкнутая цепь называется циклом. Цепь, все вершины различны, кроме, может быть её концов, называется простой. Замкнутая простая цепь называется простым циклом и обозначается , где р – число вершин.

Граф, у которого любые 2 его вершины являются смежными, называется полным графом.

Маршрут(для  ориентир графа), дуги которого различны, называется путем.

Длинной маршрута называется число ребер графа  с учетом повторений.

Две вершины  называются связными, если их соединяет  хотя бы одна простая цепь.

Отношение связности  – это отношение эквивалентности.

Граф, называют связным, если любые 2 его вершины можно соединить простой цепью.

Ребро называют перешейком, если после его удаления граф теряет свойство связности, т.е. распадается  на 2 компонента связности.

Ориентированный граф называют сильно связным, если 2 любые его вершины, можно соединить путем, т.е. и

Ориентированный граф называют слабо связным, если явл  связным граф, получающийся из орграфа  заменой всех его дуг на ребра. 
 

18. Эйлеровы и  гамильтоновы графы.

Путь в графе называется эйлеровым, если он содержит все ребра графа. Замкнутый эйлеров путь называется эйлеровым циклом. Граф, который имеет эйлеров цикл, также называется эйлеровым.

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные.

Эйлеровой цепью, называется маршрут, соединяющий две различные вершины u и v и содерж все ребра графа по одному разу.

Гамильтоновым циклом называется простой цикл, проходящий через все вершины графа по одному разу. Граф, в котором сущ  гамильтонов цикл, называется гамильтоновым. Простая цепь, проходящая через все вершины графа по одному разу называется гамильтоновой цепью.

Если в простом  графе G(V,E) с p вершинами степень любой вершины v удовлетворяет неравенству p(v)≥p/2 
 

19. Планарные  графы. Теорема Понтрягина-Куратовского.

Все графы, изоморфные другому, несут одну и ту же информацию, но их изображение может быть различным.

Граф, вершины  которого являются точками плоскости, а ребра – не прерывными плоскими линиями без самопересечений, причем никакие 2 ребра не имеют общих точек, кроме инцидентной им обоим вершинам, называется плоским.

Любой граф изоморфный плоскому графу, называется планарным.

Говорят, что  граф укладывается на плоскости (имеет плоскую укладку), если его можно представить в виде плоского графа.

Очевидно, что 1) всякий подграф планарного графа планарен.

2) граф планарен, тогда и только тогда, если  каждая связная компонента этого  графа – планарный граф.

Два графа называются гомеоморфными, если они могут быть получены из одного и того же графа подразбиением(добавление вершины на ребре) ребер.

Теорема Понтрягина-Куратовского.

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К₅ или К_3.3 
 

20. Формула Эйлера.

Формула Эйлера:

n-m+p=2, где n-число вершин, m – ребер, p-граней.

Следствие: Если в простом связном плоском графе n≥3, то m≤3n-6

Формулой Эйлера удобно пользоваться при исследовании графа на планарность. 
 

21. Раскраска  графов.

  Задачи  раскраски вершин, рёбер, граней графа  занимают важное место в теории графов. К построению раскрасок сводится ряд практических задач, например, задачи составления расписаний, проектирования технологических цепочек, распределения оборудования, раскраски географий ческой карты и т.н.

Раскраской  графа называется такое приписывание цвета его элементам (вершинам, рёбрам или граням), что никакие два смежные элемента не получают одинакового цвета.

Хроматическим числом элементов  (вершин, рёбер или граней) графа рыпается минимальное число цветов для раскраски элементов графа.

В конце XIX века была сформулирована   гипотеза    четырёх   красок:    всякий    планарный    граф    4-раскрашиваем. Попытки доказать эту гипотезу привели к следующей теореме: ВСЯКИЙ ПЛАНАРНЫЙ ГРАФ 5-РАСКРАШИВАЕМ.

На практике изображение микросхемы представляет собой граф. При изготовлении важно выяснить, можно ли схему радиоэлектронного устройства изобразить на плоскости без пересечения проводников, т.е. является ли граф планарным, возможна ли его плоская укладка. Раскраска элементов позволяет сократить затраты времени на анализ информации и корректирование процессов, изображенных в форме графа. 
 

22. Деревья. Минимальное  остовное дерево.

Существует один простой и важный тип графов, которому все авторы ли одинаковое название - деревья.

Деревом называется связный граф, не имеющий циклов.

Лесом называется любой граф без циклов.

Следовательно, деревья являются компонентами леса.

Связный ориентированный  граф без циклов называется ориентированным деревом.

Если дерево имеет п вершин, то оно имеет п-1ребро

Если  какую-либо пару несмежных вершин дерева соединить ребром, то полученный граф будет содержать ровно один цикл, и следовательно, уже не будет являться деревом.

Очевидно, что  любое ребро дерева является перешейком, после его удаления граф распадается  на две компоненты связности.

Остовом или каркасом графа G называется подграф G , содержащий те же вершины, что и G, но не имеющий циклов. Вообще говоря

С   - лес, который  на любой связной компоненте графа  G образует дерево. Если G - связный граф, то остов G   является деревом, которое будем называть остовным деревом графа G.

Граф может  иметь несколько остовов.

Обратим    внимание,    что   ВСЕ   ОСТОВЫ   одного   графа   имеют ОДИНАКОВОЕ    ЧИСЛО    РЁБЕР,    НО    ИХ    ВЕС    НИ    ЯВЛЯЕТСЯ    Величиной ПОСТОЯННОЙ ДЛЯ ДАННОГО ГРАФА,  ЗАВИСИТ ОТ ВЕСОВ ВЫЬРАнНЫХ ребер. 
 

23. Жадный алгоритм.

Требуется проложить  сеть телеграфных линий вдоль  железнодорожной сети так, чтобы все 6 станций были связаны между собой телеграфной сети и общая протяжённость сети была наименьшей.

Один из эффективных  способов решения поставленной задачи —решение с помощью алгоритма Краскала или «жадного алгоритма».

Жадный алгоритм:

1. Необходимо упорядочить множество весов
2. выбрать ребро наименьшего веса и инцидентные ему вершины и включит их в остовное дерево.
3. Исключить выбранное ребро из списка рёбер
4. повторяем шаг 2 и3 пока не построим все вершины
5. посчитать все полученного остовного дерева.

 
 

24. Алгоритм Прима.

Требуется проложить  сеть телеграфных линий вдоль  железнодорожной сети так, чтобы все 6 станций были связаны между собой телеграфной сети и общая протяжённость сети была наименьшей.

Один из эффективных  способов решения поставленной задачи —решение с помощью алгоритма Краскала или «жадного алгоритма».

Алгоритм Прима  или, как его ещё называют, алгоритм ближайшего соседа.

Анализируем матрицу  весов. Начинаем с произвольной вершины  v_i

 Шаг 1. Изучая i-ю строку матрицы весов, выбираем ребро, инцидентное v_i и имеющее наименьший вес. Выбранное ребро (v_i v_j- первое ребро остова. Удаляем его из матрицы весов.

Шаг 2. Изучая i-ю и .j-ю строки матрицы весов, выбираем ребро минмального веса, инцидентное одной из двух вершин. Присоединяем выбранное ребро к остову и удаляем из матрицы весов.

И так  далее. Процесс повторяется до тех  пор, пока в остов не будут включены все вершины графа. 
 

25. Алгоритм Дейкстры.

Алгоритм Дейкстры позволяет, решить задачу о нахождении кратчайшего пути в графе.

Особенностью  алгоритма Дейкстры является то, что  он позволяет найти кратчайшее расстояние от начальной вершины графа до всех остальных, что очень удобно, например, при моделировании сети дорог. 
 
 
 
 
 

26. Понятие потока  в сети.

Примеры сетей  и потоков в них: потоки автом  транспорта в сети автодорог, поток  грузов по железнодорожн сети, поток  телегр сообщений в сети связи  и т.д. Все эти сети имеют огранич ресурс( поток ограничен сверху).

Ориентир граф называется сетью, если он удовлетвор след условиям:

1. он связный граф без петель
2. существует ровно одна вершина, степень входа которой равна нулю(источник)
3. существует ровно одна вершина, степень выхода которой равна нулю(сток)
4. каждой дуге поставлено в соответствие неотриц число, называемое пропускной способностью

Функция φ, определенная на множестве дуг сети, называется допустимым потоком, если:

1. для любой дуги e_i выполнено условие 0≤φ≤с(e_i)

т.е. для любой  дуги допустимый поток не превышает  её пропускной способности.