Презентация, доклад по дисциплине ЕН.03 Теория вероятности и математическая статистика на тему Элементы теории графов

ТО «ЗСГК»
Хазова Е.С.

некоторые пары из которых соединены непересекающимися дугами кривых.
Точки указанного набора называются вершинами графа, а соединяющие их дуги – ребрами.
Одна из вершин графа считается начальной, другая – конечной. Тем самым на ребре устанавливается направление, которое на чертеже указывается стрелкой.
Для обозначения вершин графа используют символы v1, v2, …, vn , а для обозначения ребер или дуг – e1, e2, …, em.

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

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

через эту вершину.
Вершина степени 1 называется висячей или концевой.
Ребро, инцидентное висячей вершине, называется висячим.
Вершина степени 0 называется изолированной.

соответствующей вершины.
В графе G на рисунке: d1 = 3, d2 = 2, d3 = 0, d4 = 1, d5 = 3, d6 =1.
V3 – изолированная вершина, V4 и V6 – висячие вершины, а е2 – висячее ребро. Сумма степеней вершин равна 10. Число ребер равно 5.

в которой конец одной дуги является началом другой дуги.
Простой путь – путь, в котором ни одна дуга не встречается дважды.
Элементарный путь – путь, в котором ни одна вершина не встречается дважды.
Контур – путь, у которого конечная вершина совпадает с начальной вершиной.
Длина пути (контура) – число дуг пути (или сумма длин его дуг, если длины дуг заданы).

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

X5, X1, X2 – простой замкнутый цикл;
X1, X2, X3, X4, X5 – гомельтонова цепь;
X1, X2, X3, X4, X5, X1 – гомельтонов цикл.

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

деревьев называется лесом.

польским математиком К. Куратовским.

чтобы он не содержал внутри себя никакого подграфа, который можно было бы сжать до 5 или 6 участка.

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

Изоморфны

В-Р+Г=5-8+5=1
В-Р+Г=5-8+5=1

Для любого плоского графа:
В-Р+Г.

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

условия:
Граф связный.
Степени внутри вершин четные.
Если A – начало пути, а B – конец пути и A не совпадает с B, то их степени нечетные.
Если A – начало пути, а B – конец пути и A совпадает с B, то их степени четные.

граф не содержащий циклов.
Теорема: Всякое дерево с n-вершинами содержит (n-1) ребро.

граф не содержащий циклов.
Теорема: Всякое дерево с n-вершинами содержит (n-1) ребро.
Минимальным остовным деревом (лесом) называется остовное дерево (лес) с минимальным общим весом всех его ребер.

вершины x1.
Среди ребер, проходящих через x1, выбирается ребро x1x2 с наименьшим весом и вершина x2 включается в остовное дерево.
Среди ребер, выходящих из x1x2, ищем ребро с наименьшей длиной, допустим x, и вершину x3 включаем в оставное дерево.
Продолжаем эту процедуру, пока все вершины не будут включены в это дерево. Получим минимальное оставное дерево.
Далее необходимо доказать, что результат не зависит от выбранной первоначальной вершины.

этот граф эйлеровым?

веса в графе.

m =10 рёбер и f = 4 грани. Является ли он связным?
4. Найти хроматическое число графа.

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

алгоритмы. – М.: Вильямс, 2000. – 384 с.
Левитин, А. Алгоритмы: введение в разработку и анализ. – М.: Вильямс, 2006. – 576 с.
Спирина, М.С., Спирин, П.А. Дискретная математика. – М.: Академия, 2004. – 368 с.