Маршруты, цепи, циклы

 

39.Ориентированные графы. Диаграмма Графа. Матрицы смежности, инциденцией и достижимости.

Ориентированные графы - если условие f(vi, vj) = f(vi, vj) не задано и все элементы множества U изображаются дугами, то граф G называют ориентированным графом, или орграфом,

 

Диаграмма графа - графы принято изображать диаграммами, состоящими из кружков и линий. Кружки соответствуют вершинам графа. Линии, соединяющие кружки, соотвествуют ребрам графа.Внутри кружка пишется обозначение вершины.

 

Матрица смежности

матрица А называется матрицей смежности графа G. Это симметрическая матрица с нулями на диагонали, число единиц в строке равно степени соответствующей вершины, т.е числу инцидентных этой вершине ребер.

 

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

Матрица называется матрицей инцидентности графа G называется матрица с р строками (каждая строка соответствует одной из вершин графа) и q столбцами (каждый столбец соответствует одному из ребер графа),

 

Изоморфизм графов.

Графы называют изомрфными, если между множествами вершин можно установить взаимно однозначное соответствие, сохраняющее смежность. Отношение изоморфизма - отношение эквивалентности. Фактически, изоморфные графы - это один и тот же граф.

Маршруты, цепи, циклы.

пример маршрута: 1-2-3-5-7-4-3-5-6-2-3 пример замкнутого маршрута : 3-4-5-7-3-4-1-3  

Разрезы.

пусть G (V U) - неориентированный граф

Разрезом называется всякое множество R ребер графа G такое, что удаление этих ребер из графа делает его несвязным.

Разрез называется ппростым, если никакое его собственное подмножество разрезом не является. Разрез по-другому называют коциклом.