Графы и сети. Харитонова Е.В. - 6 стр.

UptoLike

Составители:

Рубрика:

1. ГРАФЫ

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

● Граф есть конечное множество V, называемое множеством вершин, и

множество Е двухэлементных подмножеств множества V. Множество Е назы-

вается множеством ребер. Элемент множества Е называется ребром. Граф обо-

значается G(V, E). Элементы a и b элементы множества V называются соеди-

ненными или

связанными ребром {a, b}, если {a, b}

∈

Е.

Обычно конечный граф изображают в виде диаграммы, на которой вер-

шины обозначаются точками, а ребра, соединяющие две вершины, – линиями

между этими точками.

● Если {a, b} – ребро, тогда вершины a и b называются концами ребра {a,

b}. Ребро {a, b} называют также инцидентным к вершинам a и b.

●

Две вершины называются смежными, если они являются концами реб-

ра, или, что то же самое, если они инцидентны к одному ребру.

● Два ребра называются смежными, если они инцидентны к общей вер-

шине.

Пример. Граф с множеством вершин V = {a, b, c} и множеством ребер Е = {{a, b},{b,

c}}может быть изображен, как показано на рис.1.1 или рис.1.2.

Рис. 1.1 Рис. 1.2

Пример. Граф, у которого V = {a, b, c, d, e} и Е = {{a, b},{a, e},{b, e},{b, d},{b, c},{c,

d}} может быть изображен диаграммой, показанной на рис. 1.3.

Рис. 1.3

a c