Презентация, доклад по дискретной математике на тему Граф. Ориентированный граф, для студентов 2 курса специальности 09.02.01

М.А
по учебникам:
М.С. Спирина, П.А. Спирин Дискретная математика: Учебник для студ. учреждений сред. проф. образования –М.: Издательский центр «Академия»
Могилев А.В., Пак Н. И., Хеннер Е.К.. Информатика. Учеб. пособие для студ. пед. вузов. – 4-е изд., стер. - М.: Издательский центр «Академия»

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

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

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

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

вершина 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.

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

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

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

с первой вершиной следующего, называется маршрутом.
Число ребер маршрута называется длиной маршрута. Например, в HCDFD — маршрут длиной 4. Обозначение: |HCDFD| = 4.
Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом. В графе 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, F2) = min|F,...F2|.

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

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

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

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

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

F2 (а) – неполное ветвление. Развитием блок-схемы типа альтернатива является блок-схема выбор ( б).

использовать и другие графические знаки:
а) типовой процесс (обращение к подпрограмме);
б) начало или конец алгоритма;
в) подготовка к циклическому процессу;
г) ввод и вывод данных.