1.1 Определения и примеры
Граф G=(V, Е) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами. Каждое ребро определяется парой вершин.
Если ребра графа определяются упорядоченными парами вершин, то G называется направленным или ориентированным графом. В противном случае G называется ненаправленным или неориентированным графом. Для обозначения вершин графа будем использовать символы v1, v2, v3,…, а для обозначения ребер - е1, е2, е3, . . . . Вершины vi и vj, определяющие ребро ei, называются концевыми вершинами ребра еi. В этом случае ребро еi обозначается как ei=(vi, vj). Заметим, что в множестве Е допускается более чем одно ребро с одинаковыми концевыми вершинами. Все ребра с одинаковыми концевыми вершинами называются параллельными. Кроме того, концевые вершины ребра не обязательно различны. Если еi= (vi, vi), то ребро ei называется петлей. Граф называется простым, если он не содержит петель и параллельных ребер. Граф G является графом порядка n, если множество его вершин состоит из n элементов.Граф, не имеющий ребер, называется пустым. Граф, не имеющий вершин (и, следовательно, ребер), называется нуль-графом.
Графически граф может быть представлен диаграммой, в которой вершина изображена точкой или кружком, а ребро — отрезком линии, соединяющим точки или кружки, соответствующие концевым вершинам ребра. Например, если V={v1 v2, v3, v4, v5, v6} и E= {e1, e2, e3, e4, e5}, такие, что e1=(v1, v2), e2=(v1, v4), e3= (v5, v6), e4= (v1, v2), e5=(v5,v5), тогда граф G=(V, E) представляется так, как изображено на рис. 1. В этом графе е1 и e4 - параллельные ребра, е5 - петля. Говорят, что ребро инцидентно своим концевым вершинам. Две вершины смежны, если они являются концевыми вершинами некоторого ребра. Если два ребра имеют общую концевую вершину, они называются смежными.
Рисунок 1
Например, в графе на рис.
1 ребро е1 инцидентно вершинам v1 и v2; v1 и v4 являются смежными вершинами, а е1 и е2 - смежными ребрами.Число инцидентных вершине vi ребер называется степенью вершины и обозначается d(vi). Иногда степень вершины называется также ее валентностью. Вершина степени 1 называется висячей вершиной. Единственное ребро, инцидентное висячей вершине, называется висячим. Вершина степени 0 называется изолированной. По определению петля при вершине vi добавляет 2 в степень соответствующей вершины. Величины δ(G) и ∆(G) обозначают минимальную и максимальную степени вершины в G соответственно.
В графе G на рис. 1 d(v1) = 3, d(v2) = 2, d(v3) = 0, d (v4) = 1, d (v5) = 3, d(v6) = 1.
Заметим, что v3- изолированная вершина, v4 и v6- висячие вершины, е2 — висячее ребро. Легко проверить, что сумма степеней вершин в данном графе G равна 10, тогда как число ребер равно 5. Таким образом, сумма степеней вершин графа G равна удвоенному числу ребер графа G и, следовательно, является четным числом. Более того, можно показать, что число вершин графа G нечетной степени также четно. Эти результаты свойственны не только графу на рис. 1.
Еще по теме 1.1 Определения и примеры:
- 3.1 Определения и примеры
- 27.Вычисление площадей плоских фигур с помощью определенного интеграла. Примеры.
- 6. Примеры определения параметров пласта по индикаторным диаграммам
- Определение рыночной добавленной стоимости (MVA) для базового примера
- Определение экономической добавленной стоимости (EVA) для базового примера
- 23.Метод интегрирования по частям для случаев неопределенного и определенного интегралов (вывести формулу). Примеры.
- 1.Понятие функции, способы задания функций. Область определения. Четные и нечетные, ограниченные, монотонные функции. Примеры.
- 18.Функции нескольких переменных. Примеры. Частные производные (определение). Экстремум функции нескольких переменных и его необходимые условия.
- 31,32.Определение числового ряда. Сходимость числового ряда. Необходимый признак сходимости рядов (доказать). Примеры.
- Факт смерти лица в определенное время и при определенных обстоятельствах
- В частности, определение договора лизинга в основном приведено в соответствие с определением,
- Метод 2. «Определение убеждений»Техника 1. «Определение ожиданий»
- Само по себе определение права через свободу еще не преодолевает главного недостатка других определений права -
- Термины даются на русском, английском и датском языках (в указанной последовательности). Цифры в скобках указывают номера определений, от которых зависит данное определение.
- 24.Определенный интеграл как предел интегральной суммы. Свойства определенного интеграла.
- Ж) Лишение права занимать определенные должности или заниматься определенной деятельностью (дисквалификация)