Определение. Если (а, b) – ориентированное ребро, тогда вершина а называется начальной вершиной ориентированного графа, а вершина b – конечной вершиной ребра (а, b). Ориентированное ребро (а, b) называют также инцидентным вершинам а и b. Обратно, говорят, что вершины а и bинцидентны ориентированному ребру (а, b).
Пример 1. Рассмотрим ориентированный граф G1, который состоит из множества вершин V(G1), содержащего 6 элементов, и множества рёбер E(G1), содержащего 6 элементов: V(G1) = {a, b, c, d, e, f}, E(G1) = {(a, b), (a, c), (b, d), (c, d), (e, c), (f, d)}. Визуальное представление ориентированного графа G1:
В ориентированном графе G1 (рисунок орграфа выше) вершина а инцидентна ориентированным рёбрам (a, c) и (a, b), вершина b инцидентна двум рёбрам (a, b) и (b, d), вершина с инцидентна трём рёбрам (a, c), (c, d) и (e, c), вершина d инцидентна трём рёбрам (b, d), (c, d) и (f, d), вершина e инцидентна ребру (e, c), вершина f инцидентна ребру (f, d).
Также верно, что в ориентированном графе G1 ребро (а, b) инцидентно вершинам a и b, ребро (a, c) инцидентно вершинам a и c, ребро (b, d) инцидентно вершинам b и d, ребро (c, d) инцидентно вершинам c и d, ребро (e, c) инцидентно вершинам c и e, ребро (f, d) инцидентно вершинам d и f.
Рассмотрим ориентированный граф G2, который состоит из множества вершин V(G2), содержащего 6 элементов, и множества рёбер E(G2), содержащего 5 элементов: V(G2) = {a, b, c, d, e, f}, E(G2) = {(a, c), (b, e), (c, d), (d, e), (f, d)}. Визуальное представление ориентированного графа G2:
В ориентированном графе G2 вершина а инцидентна ребру (a, c), вершина bинцидентна ребру (b, e), вершина с инцидентна двум рёбрам (a, c) и (c, d), вершина d инцидентна трём рёбрам (c, d), (d, e) и (f, d), вершина e инцидентна двум рёбрам (b, e) и (d, e), вершина f инцидентна ребру (f, d).
В ориентированном графе G2 ребро (a, c) инцидентно вершинам a и c, ребро (b, e) инцидентно вершинам b и e, ребро (c, d) инцидентно вершинам c и d, ребро (d, e) инцидентно вершинам d и e, ребро (f, d) инцидентно вершинам d и f.
Определения. Степенью входа (полустепенью захода) вершины v, принадлежащей ориентированному графу – обозначается indeg(v) – называется число рёбер, для которых вершина v является конечной.
Степенью выхода (полустепенью исхода) вершины v, принадлежащей ориентированному графу – обозначается outdeg(v) – называется число рёбер, для которых вершина vявляется начальной.
Если indeg(v) = 0, то вершина v называется источником (истоком), если outdeg(v) = 0, то вершина v называется стоком. Если у вершины v и indeg(v) = 0, и outdeg(v) = 0, то она называется изолированной.
Степень вершины v, принадлежащей ориентированному графу, обозначается deg(v) и определяется как сумма степеней входа и выхода, т. е. определяется числом ориентированных рёбер графа, инцидентных вершине v.
Пример 2. В ориентированном графе G1 степени входа и выхода каждой вершины определены, как показано в таблице ниже.
Из информации, показанной в этой таблице, видно, что в графе G1 источниками являются вершины a, e и f, а стоком является вершина d.
В ориентированном графе G2 степени входа и выхода каждой вершины определены, как показано в следующей таблице.
Из информации, показанной в последней таблице, видно, что в графе G2 источниками являются вершины a, b и f, а стоком является вершина e.
Определение. Две вершины называются смежными, если они инцидентны одному ребру. Два ребра называются смежными, если они инцидентны общей вершине.
Определение. Множество вершин графа, смежных с вершиной v, обозначается adj(v).
Пример 3. В ориентированном графе G1 смежными являются следующие пары вершин: a и b, a и c, b и d, c и d, c и e, d и f, множества каждой вершины графа G1 занесены в таблицу ниже.
Не являются смежными, например, вершины а и e, а также b и f. В графе G1 смежными являются следующие пары ориентированных рёбер: (a, b) и (a, c), (a, b) и (b, d) — а также тройки (a, c), (c, d), (e, c) и (b, d), (c, d), (f, d).
Не являются смежными, например, рёбра (a, c) и (b, d).
В ориентированном графе G2 смежными являются следующие пары вершин: a и c, b и e, c и d, d и e, d и f, множества вершин занесены в следующую таблицу.
Не являются смежными, например, вершины а и d, а также b и d.
В графе G2 смежными являются следующие пары ориентированных рёбер: (a, c) и (c, d), (b, e) и (d, e) – а также тройка (c, d), (d, e) и (f, d).
Определение.
Упражнение. Для следующих ориентированных графов (выберите 1 строку с ориентированными графами):
1) запишите множество ориентированных рёбер, инцидентных вершинам орграфа;
2) запишите множество вершин, смежных с вершинами орграфа;
3) определите степень каждой вершины орграфа;
4) определите степени входа (выхода) каждой вершины орграфа;
5) определите и укажите, если есть, источники и стоки в орграфе.
Обратите внимание на комментарии других читателей, постарайтесь в своих ответах не повторяться с ними.