Графы и их элементы

Сентябрь 13, 2022

Главная
Математика
Графы и их элементы

Содержание

2. Графом G = (V, X) называется пара двух конечных множеств: множество точек и множество линий X,
3. Пусть дан граф G = (V, X), где v = [V, W, ...} — конечное непустое
4. Граф G( V, X) может иметь ребра с одинаковыми парами вида Х(V, W). Такие ребра называются
5. Теорема 1. В графе G(V,Х) сумма степеней всех его вершин — число четное, равное удвоенному числу
6. Теорема 2. Число нечетных вершин любого графа — четно. Следствие.Невозможно начертить граф с нечетным числом нечетных
7. Граф G называется полным,если любые две его различные вершины соединены одним и только одним ребром. Дополнением
8. Если все пары (Vi , Vj) во множестве X являются упорядоченными, т.е. кортежами длины 2, то
9. Последовательность попарно инцидентных вершин Vi1 , Vi2, ..., V ik неориентированного графа, т.е. последовательность ребер неориентированного
10. В орграфе маршрут является ориентированным и называется путем. Другими словами, путь— упорядоченная последовательность ребер ориентированного графа,
11. Теорема 3. Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая
12. Ребро (V, W) связного графа G называется мостом, если после его удаления G станет несвязным и
13. Теорема 4. Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.
15. Скачать презентацию

Слайд 2

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

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

Примеры графов: а — со смежными вершинами; 6 — полный; в – со смежными ребрами; г — с петлей

Слайд 3

Пусть дан граф G = (V, X), где v = [V, W, ...} — конечное

непустое множество его вершин, а Х(V, W) — его ребра. Если ребро графа G соединяет две его вершины V и W (т.е. ÎX), то говорят, что это ребро им инцидентно.
Две вершины графа называются смежными, если существует инцидентное им ребро.
Если граф G имеет ребро Х(V, W), у которого начало и конец совпадают, то это ребро называется петлей.
Два ребра называются смежными, если они имеют общую вершину.

Слайд 4

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

называются кратными, или параллельными.
Количество одинаковых пар вида Х(V, W) называется кратностью ребра (V, W).
Вершина графа, имеющая степень, равную нулю, называется изолированной.
Граф, состоящий из изолированных вершин, называется нуль-графом.
Вершина графа, имеющая степень, равную 1, называется висячей.

Слайд 5

Теорема 1.
В графе G(V,Х) сумма степеней всех его вершин — число четное, равное

удвоенному числу ребер графа:
где п = ïVï — число вершин; т = ïХï — число ребер графа.
Вершина называется четной (нечетной ) если ее степень четное (нечетное) число.

Слайд 6

Теорема 2.
Число нечетных вершин любого графа — четно.
Следствие.Невозможно начертить граф с нечетным числом

нечетных вершин.

Слайд 7

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

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

Слайд 8

Если все пары (Vi , Vj) во множестве X являются упорядоченными, т.е. кортежами длины 2, то

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

Слайд 9

Последовательность попарно инцидентных вершин Vi1 , Vi2, ..., V ik неориентированного графа, т.е. последовательность ребер неориентированного

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

Слайд 10

В орграфе маршрут является ориентированным и называется путем. Другими словами, путь— упорядоченная последовательность

ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны.
Цикл в орграфе — путь, у которого совпадают начало и конец.
Цепь, путь и цикл в графе называются простыми, если они проходят через любую из вершин не более одного раза.
Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут.
Две вершины называются связными, если существует маршрут между ними.
Граф G можно разбить на непересекающиеся подмножества Хi по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств — несвязны. Тогда все подграфы Vi(классы эквивалентности) графа G называют связными компонентами, или компонентами связности.Связный граф имеет одну компоненту связности.

Слайд 11

Теорема 3.
Для того чтобы связный граф G являлся простым циклом, необходимо

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

Слайд 12

Ребро (V, W) связного графа G называется мостом, если после его удаления G станет несвязным и

распадется на два связных графа G ' и G ". На рисунке мост (СЕ) разделил связный граф G7 на два различных связных графа: G ' с вершинами (А,В, С,D) и G " с вершинами (Е, F, G,Н,I). Также мостом является ребро ЕС.

Граф G7 с мостами BC и CE

Слайд 13