8

Теория графов

Неориентированные графы

Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин a; b.

Теория графов

Неориентированные графы

Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин a; b.

Определение. Ребро, сопосталенное паре fa; ag называется петлей. Если несколько ребер сопоставлеы одной и той же паре вершин fa; bg, то такие ребра называют кратными.

Теория графов

Неориентированные графы

Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин a; b.

Определение. Ребро, сопосталенное паре fa; ag называется петлей. Если несколько ребер сопоставлеы одной и той же паре вершин fa; bg, то такие ребра называют кратными.

Определение. Неориентированный граф (V ; E) называется простым, если среди элементов V нет петель и кратных ребер.

Теория графов

Неориентированные графы

Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин a; b.

Определение. Ребро, сопосталенное паре fa; ag называется петлей. Если несколько ребер сопоставлеы одной и той же паре вершин fa; bg, то такие ребра называют кратными.

Определение. Неориентированный граф (V ; E) называется простым, если среди элементов V нет петель и кратных ребер. Для случая простых графов мы будем отождествлять ребра e 2 E с соответствующей парой вершин fa; bg 2 V 2.

Теория графов

Отношения инцидентности и смежности

Пусть дан неориентированный граф G = (V ; E).

Определение. Если ребру e 2 E сопоставлена пара вершин fa; bg 2 V 2, то будем говорить, что ребро e инцидентно каждой из вершин a и b

Теория графов

Отношения инцидентности и смежности

Пусть дан неориентированный граф G = (V ; E).

Определение. Если ребру e 2 E сопоставлена пара вершин fa; bg 2 V 2, то будем говорить, что ребро e инцидентно каждой из вершин a и b (а также, вершины a и b являются концами ребра e).

Теория графов

Отношения инцидентности и смежности

Пусть дан неориентированный граф G = (V ; E).

Определение. Если ребру e 2 E сопоставлена пара вершин fa; bg 2 V 2, то будем говорить, что ребро e инцидентно каждой из вершин a и b (а также, вершины a и b являются концами ребра e).

Определение. Если имеется ребро e 2 E, сопоставленное паре вершин fa; bg 2 V 2, то будем говорить, что вершины a и v являются смежными.

Теория графов

Матрица инцидентности.

Пусть дан неориентированный граф G = (V ; E).

V = f1; 2; : : : ; ng: E = f1; 2; : : : ; mg:

Определение. Матрица A = (aij ) размера m n называется матрицей инцидентности графа G, если

Теория графов

Матрица инцидентности.

Пусть дан неориентированный граф G = (V ; E).

V = f1; 2; : : : ; ng: E = f1; 2; : : : ; mg:

Определение. Матрица A = (aij ) размера m n называется матрицей инцидентности графа G, если

Теория графов

Степени вершин графа.

Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза.