8
.pdfТеория графов
Ориентированные графы
Определение. Ориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру
e 2 E сопоставлена упорядоченная пара вершин (a; b).
Теория графов
Неориентированные графы
Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин
fa; bg.
Теория графов
Неориентированные графы
Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин
fa; bg.
Определение. Ребро, сопоставленное паре fa; ag называется петлей. Если несколько ребер сопоставлены одной и той же паре вершин fa; bg, то такие ребра называют кратными.
Теория графов
Неориентированные графы
Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин
fa; bg.
Определение. Ребро, сопоставленное паре fa; ag называется петлей. Если несколько ребер сопоставлены одной и той же паре вершин fa; bg, то такие ребра называют кратными.
Определение. Неориентированный граф (V ; E) называется простым, если среди элементов V нет петель и кратных ребер.
Теория графов
Неориентированные графы
Определение. Неориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e 2 E сопоставлена неупорядоченная пара вершин
fa; bg.
Определение. Ребро, сопоставленное паре fa; ag называется петлей. Если несколько ребер сопоставлены одной и той же паре вершин fa; bg, то такие ребра называют кратными.
Определение. Неориентированный граф (V ; E) называется простым, если среди элементов V нет петель и кратных ребер. Для случая простых графов мы будем отождествлять ребра e 2 E с соответствующей парой вершин
fa; bg 2 D(V ) = ffc; dgjc; d 2 V g.
Теория графов
Отношения инцидентности и смежности
Пусть дан неориентированный граф G = (V ; E).
Определение. Если ребру e 2 E сопоставлена пара вершин fa; bg 2 D(V ), то будем говорить, что ребро e инцидентно каждой из вершин a и b
Теория графов
Отношения инцидентности и смежности
Пусть дан неориентированный граф G = (V ; E).
Определение. Если ребру e 2 E сопоставлена пара вершин fa; bg 2 D(V ), то будем говорить, что ребро e инцидентно каждой из вершин a и b (а также, вершины a и b являются концами ребра e).
Теория графов
Отношения инцидентности и смежности
Пусть дан неориентированный граф G = (V ; E).
Определение. Если ребру e 2 E сопоставлена пара вершин fa; bg 2 D(V ), то будем говорить, что ребро e инцидентно каждой из вершин a и b (а также, вершины a и b являются концами ребра e).
Определение. Если имеется ребро e 2 E, сопоставленное паре вершин fa; bg 2 D(V ), то будем говорить, что вершины a и b являются смежными.
Теория графов
Матрица инцидентности.
Пусть дан неориентированный граф G = (V ; E).
V = f1; 2; : : : ; ng: E = f1; 2; : : : ; mg:
Определение. Матрица A = (aij ) размера m n называется матрицей инцидентности графа G, если
|
> |
0; |
если ребро iне инцидентно вершине j; |
|
|
|
||||||||||
aij = |
< |
|
; |
если ребро i |
|
|
|
|
|
|
|
|
|
: |
|
|
81; |
не является петлей и инцидентно j; |
|||||||||||||||
|
>2 |
|
если ребро i |
является петлей и инцидентно j |
|
|
|
|||||||||
|
: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теория графов
Матрица инцидентности.
Пусть дан неориентированный граф G = (V ; E).
V = f1; 2; : : : ; ng: E = f1; 2; : : : ; mg:
Определение. Матрица A = (aij ) размера m n называется матрицей инцидентности графа G, если
|
> |
0; |
если ребро iне инцидентно вершине j; |
|
|
aij = |
< |
|
; |
|
: |
81; |
если ребро i не является петлей и инцидентно j; |
||||
|
>2 |
|
если ребро i является петлей и инцидентно j |
|
|
|
: |
|
|
n |
|
jP1 |
aij = 2: |
||||||||||
Для каждого i 2 E имеем |
|||||||||||
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|