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

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

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

Вершины v₂ и v₄ инцидентны ребру х₅

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

Ребра х₁,х₂,х₅  смежные, т.к. инцидентны вершине v₂

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

d(v₂) =3, вершина v₅ - висячая, вершина v₆ - изолированная

Маршрут (путь) для графа G(V,X) - последовательность v₁x₁v₂x₂v₃...x_kv_k+1.

v₁x₁v₂x₂v₃x₃v₄x₅v₂

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

Если M=v₁x₁v₂x₂v₃x₃v₄x₅v₂, то |М|=4

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

v₁x₁v₂x₂v₃x₃v₄x₅v₂x₁v₁

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

v₂x₂v₃x₃v₄

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

v₂x₂v₃x₃v₄x₅v₂

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

Вершины v₁ и v₃ связные, т.к. ∃ v₁x₁v₂x₂v₃

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