Перечень ребер

Для хранения перечня ребер используют двумерный массив размерности |Е| х 2, каждая строка которого описывает ребро графа.

Для графа, изображенного на рисунке 15 перечень ребер имеет вид:

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

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

На рисунке 17 изображены изоморфные графы.

Достижимость и связность

Определение. Маршрут – это последовательность ребер (дуг) графа, в которой конец каждого ребра (дуги) совпадает с началом следующего ребра.

Определение. Число ребер маршрута называется его длиной.

Определение. Циклом называется замкнутый маршрут.

Например, в графе, изображенном на рисунке 18, вершины v₅ и v₃ соединены маршрутами (е₆, е₂) длины 2; (е₅, е₁, е₂) длины 3. Маршрут (е₅, е₁, е₂, е₃, е₄) является циклом.

Определение. Если существует маршрут из вершины графа v в вершину u, то говорят, что u достижима из v.

Дата добавления: 2014-12-29; Просмотров: 548; Нарушение авторских прав?; Мы поможем в написании вашей работы!