| Понятие | Пример |
|---|---|
| Граф G(V,X) представляет собой непустое множество вершин V={v1,v2,…,vn} и множество ребер X, оба конца которых принадлежат множеству V | |
| Если х=(v1,v2) — ребро графа, то вершины v1 и v2 инцидентны ребру х | Вершины v2 и v4 инцидентны ребру х5 |
| Два ребра, инцидентные одной вершине, — смежные | Ребра х1,х2,х5 смежные, т.к. инцидентны вершине 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 |
| Два графа изоморфны,если существует взаимно-однозначное соответствие между множествами их вершин и ребер |
