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

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

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here