Основные понятия теории графов (Таблица)

Понятие

Пример

Граф G(V,X) представляет собой непустое множество вершин V={v1,v2,...,vn} и множество ребер X, оба конца которых принадлежат множеству V

mat 12 39

Если х=(v1,v2) - ребро графа, то вершины v1 и v2 инцидентны ребру х

Вершины v2 и v4 инцидентны ребру х5

Два ребра, инцидентные одной вершине, - смежные

Ребра х125  смежные, т.к. инцидентны вершине v2

Степень вершины d(v) графа - число ребер, которым эта вершина инцидентна. Если d(v)=0, то вершина изолированная,если d(v)=1, то висячая

d(v2) =3, вершина v5 - висячая, вершина v6 - изолированная

Маршрут (путь) для графа G(V,X) - последовательность v1x1v2x2v3...xkvk+1.

v1x1v2x2v3x3v4x5v2

Длина маршрута - количество ребер в нем

Если M=v1x1v2x2v3x3v4x5v2, то |М|=4

Маршрут замкнутый, если его начальная и конечная точки совпадают, т.е. v1=vk+l

v1x1v2x2v3x3v4x5v2x1v1

Незамкнутый маршрут (путь) - цепь. Цепь, в которой все вершины попарно различны, называется простой цепью

v2x2v3x3v4

Замкнутый маршрут (путь) - цикл (контур). Цикл, в котором все вершины попарно различны, называется простым циклом.

v2x2v3x3v4x5v2

Две вершины графа связные, если существует соединяющая их простая цепь

Вершины v1 и v3 связные, т.к. ∃ v1x1v2x2v3

Два графа изоморфны,если существует взаимно-однозначное соответствие между множествами их вершин и ребер

mat 12 40

 



1 1 1 1 1 1 1 1 1 1 Рейтинг 5.00 [1 Голос]

Поделитесь ссылкой с друзьями:


Подписываемся !!!

Комментарии:

comments powered by HyperComments

библиотеки Яндекс.Метрика