Лекция по теме "Графы в дискретной математике"
Оценка 4.7 (более 1000 оценок)

Лекция по теме "Графы в дискретной математике"

Оценка 4.7 (более 1000 оценок)
Контроль знаний +3
pptx
математика
19.02.2020
Лекция по теме "Графы в дискретной математике"
Презентация к лекции по теме "Графы в дискретной математике"
лекция Графы.pptx

Лекция 11-12 Введение в теорию графов

Лекция 11-12 Введение в теорию графов

Лекция 11-12 Введение в теорию графов

Вопросы лекции:
Основные понятия и определения
Типы графов
Графическое представление алгоритмов

Основные понятия и определения

Основные понятия и определения

1. Основные понятия и определения

Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёнинг.
Но первая работа по теории графов принадлежала Леонарду Эйлеру и была написана еще в 1736 г.
С помощью графов изображаются:
схемы различных дорог,
линии воздушных сообщений,
газопроводов,
теплотрасс,
электросетей,
микросхемы,
дискретные многошаговые процессы,
системы различных бинарных отношений,
химические структурные формулы
другие диаграммы и схемы.
Без графов сложно анализировать классификации в различных науках.

Графом G = (V, X) называется пара двух конечных множеств: множество точек (V) и множество линий (X), соединяющих некоторые пары точек

Графом G = (V, X) называется пара двух конечных множеств: множество точек (V) и множество линий (X), соединяющих некоторые пары точек

Графом G = (V, X) называется

пара двух конечных множеств:
множество точек (V) и
множество линий (X), соединяющих некоторые пары точек.
Точки называются вершинами (узлами) графа, линии – ребрами графа.

Примеры графов

Примеры графов

Примеры графов

Дан граф G=(V,X), где V={V,W,…} – конечное непустое множество его вершин, а

Дан граф G=(V,X), где V={V,W,…} – конечное непустое множество его вершин, а

Дан граф G=(V,X), где V={V,W,…} – конечное непустое множество его вершин, а X(V,W) – его ребра.
Если ребро графа G соединяет две его вершины V и W то говорят, что это ребро им инцидентно.
Две вершины графа называются смежными, если существует инцидентное им ребро: на рисунке а) смежные вершины - A и B, A и C.
Если граф G имеет ребро X(V,V), у которого начало и конец совпадают, то это ребро называется петлей. На рисунке г) петля – q(C,C).
Два ребра называются смежными, если они имеют общую вершину. На рисунке в) смежными являются, например, ребра х1 и х2 с общей вершиной С.

Граф G(V,X) может иметь ребра с одинаковыми парами вида

Граф G(V,X) может иметь ребра с одинаковыми парами вида

Граф G(V,X) может иметь ребра с одинаковыми парами вида X(V,W). Такие ребра называются кратными, или параллельными ( а) x1(A,B),x2(A,B) - кратные ребра)
Количество одинаковых пар вида x(V,W) называется кратностью ребра (V,W).
На рисунке а) ребро АС имеет кратность, равную 3, а ребро АВ – кратность, равную 2.
Число ребер, инцидентных вершине А, называется степенью этой вершины и обозначается deg(A).
Если вершине инцидента петля, она дает вклад в степень, равный двум, так как оба конца приходят в эту вершину.

На рисунке в) , вершина А имеет степень, равную 1,

На рисунке в) , вершина А имеет степень, равную 1,

На рисунке в), вершина А имеет степень, равную 1, С- 4 вершина D- 2.
Записывается это в виде: deg(A)=1, deg(C)=4, deg(D)=2.
Граф G4 рисунок г) содержит четыре вершины V={A, B, C, D} и шесть ребер : deg(A)=3, deg(В)=3, deg(C)=3, deg(D)=2.

Типы графов Вершина графа, имеющая степень, равную нулю, называется изолированной

Типы графов Вершина графа, имеющая степень, равную нулю, называется изолированной

2. Типы графов

Вершина графа, имеющая степень, равную нулю, называется изолированной.
Граф, состоящий из изолированных вершин, называется нуль-графом. Для нуль-графа Х= .
Вершина графа, имеющая степень, равную 1, называется висячей на рисунке г, вершина Е – изолированная: deg(E)=0, а вершины A, B,E, G, H на рисунке в) – висячие.
Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Полным является граф G2 на рисунке б).

Дополнением графа G(V, X) называется граф (V,

Дополнением графа G(V, X) называется граф (V,

Дополнением графа G(V, X) называется граф (V, X) с теми же вершинами V, что и граф G, и имеющий те и только те ребра Х, которые необходимо добавить к графу G, чтобы он стал полным. Например, дополнением графа G5 до графа G2 на рис. б) является граф 5
Дополнением полного графа будет нуль-граф, и наоборот.

Тема 3.2 Различные графы Ориентированные графы

Тема 3.2 Различные графы Ориентированные графы

Тема 3.2 Различные графы

Ориентированные графы.
Эйлеровы и Гамильтоновы графы.
Деревья. Лес. Разрезы.

Ориентированный граф Если все пары (Vh

Ориентированный граф Если все пары (Vh

Ориентированный граф

Если все пары (Vh Vj) во множестве X являются упорядоченными, т. е. кортежами длины 2, то граф называется ориентированным, орграфом, или направленным.
В таком случае ребра принято изображать стрелками.

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

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

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

Графическое представление алгоритмов

Графическое представление алгоритмов

Графическое представление алгоритмов

Блок-схема — это ориентированный граф, указывающий порядок исполнения команд алгоритма.
Вершины такого графа могут быть одного из трех типов:
функциональная вершина (F);
предикатная вершина (Р), (t, т.е. true, означает «истина», f, т.е. false, — «ложь»);
объединяющая вершина (вершина «слияния») (U).

Иногда вместо t пишут «да» (либо знак «+»), вместо f— «нет» (либо знак «-»).

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

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

Последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом.
Число ребер маршрута называется длиной маршрута. Например, в HCDFD — маршрут длиной 4. Обозначение: |HCDFD| = 4.

Маршрут называется цепью , если все его ребра различны, и простой цепью, если все его вершины (а, следовательно, и ребра), кроме, возможно, крайних, различны

Маршрут называется цепью , если все его ребра различны, и простой цепью, если все его вершины (а, следовательно, и ребра), кроме, возможно, крайних, различны

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины (а, следовательно, и ребра), кроме, возможно, крайних, различны. Маршрут называется циклическим, если V1=VL+1 (замкнутый маршрут).
Циклическая цепь называется циклом, а циклическая, простая цепь – простым циклом (все его n вершин различны). Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом (цепью или простой цепью).
Длина всякого простого цикла не менее трех, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом, обозначается g(G). Окружение графа G (обозначается с(G)) – длина самого длинного простого цикла графа G. Эти понятия не определены, если в G нет циклов.

Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом

Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом

Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом. В графе G4:
(t, s, р, r), (и, s, t, r) — циклы длиной 4, (r, t, q, s, и) — цикл длиной 5,
(t, s, и, r, t, s, р, r) — 8-цикл,
(р,и) — 2-цикл, петля (q) — 1-цикл.
Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами. Обозначается как d( V1, V2) (от лат. distantio — расстояние) d( V1, V2) = min|V,...V2|.

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

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

Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут. Для связного графа ориентация дуг не обязательна. Так, граф G2 является связным, а граф С4— несвязным. Также можно ввести понятие связности для вершин графа: две вершины называются связными, если существует маршрут между ними.

Ребро ( V, W) связного графа

Ребро ( V, W) связного графа

Ребро (V, W) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа (G’ и G”). На рис. мост (СЕ) разделил связный граф G, на два различных связных графа: G’ с вершинами (A,B,C,D) и G” с вершинами (Е, F, G, Н, I). Также мостом является ребро ВС.

Графы G8’ и G8” называются изоморфными, если существует взаимно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вершины

Графы G8’ и G8” называются изоморфными, если существует взаимно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вершины

Графы G8’ и G8” называются изоморфными,

если существует взаимно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вершины

Граф G называется планарным (плоским), если существует изоморфный ему граф

Граф G называется планарным (плоским), если существует изоморфный ему граф

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

скачать по прямой ссылке

150.000 призовой фонд • 11 почетных документов • Свидетельство публикации в СМИ