39.Ориентированные графы. Диаграмма Графа. Матрицы смежности, инциденцией и достижимости.
Ориентированные графы - если условие f(vi, vj) = f(vi, vj) не задано и все элементы множества U изображаются дугами, то граф G называют ориентированным графом, или орграфом,
Диаграмма графа - графы принято изображать диаграммами, состоящими из кружков и линий. Кружки соответствуют вершинам графа. Линии, соединяющие кружки, соотвествуют ребрам графа.Внутри кружка пишется обозначение вершины.
Матрица смежности
матрица А называется матрицей смежности графа G. Это симметрическая матрица с нулями на диагонали, число единиц в строке равно степени соответствующей вершины, т.е числу инцидентных этой вершине ребер.
Матрица инцидентности
Матрица называется матрицей инцидентности графа G называется матрица с р строками (каждая строка соответствует одной из вершин графа) и q столбцами (каждый столбец соответствует одному из ребер графа),
Изоморфизм графов.
Графы называют изомрфными, если между множествами вершин можно установить взаимно однозначное соответствие, сохраняющее смежность. Отношение изоморфизма - отношение эквивалентности. Фактически, изоморфные графы - это один и тот же граф.
Разрезы.
пусть G (V U) - неориентированный граф
Разрезом называется всякое множество R ребер графа G такое, что удаление этих ребер из графа делает его несвязным.
Разрез называется ппростым, если никакое его собственное подмножество разрезом не является. Разрез по-другому называют коциклом.