Маршруты, цепи, циклы. Связность

Определение 6 (Маршрут). Маршрутом в графе G = <V,E; I> называется последовательность вершин и рёбер вида v0,e1,v1,e2,..., vn-1,en,vn, где vi О V, i О [0,n], ei О E, (vi-1,ei), (vi,ei) О I, i О [1,n]. Вершины v0, vn называются связанными данным маршрутом (или просто связанными). Вершину v0 называют началом, а vn – концом маршрута. Если v0 = vn, то маршрут называют замкнутым. Число n называется длиной маршрута.

41*. Изоморфизм графов (1). Операции над графами (2). Гомеоморфизм графов (3).

1)

2)

3)

Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.

Определение. Орграф D1 называется подразбиением орграфа D2, если орграф D1 можно получить из D2 путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.

Определение. Орграфы D1, D2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.

42. Представления графов. Матрицы смежности, инцидентности, весов графа (1). Список ребер графа (2).

1)

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i -й вершины графа в j -ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i -й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i -й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

· a_ij — число рёбер, связывающих вершины Vi и Vj, причем в некоторых приложениях каждая петля (ребро {vi и vj} при некотором i) учитывается дважды.

· Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.