Флеш-карточки по основам теории графов

Question 1

Что такое граф $G=(V,E)$?

Accepted Answer

Граф — это упорядоченная пара $G=(V,E)$, где $V$ — множество вершин (узлов), а $E$ — множество рёбер, каждое ребро соединяет две вершины (в неориентированном графе ребро — это неупорядоченная пара $\{u,v\}$).

Question 2

В чём разница между маршрутом (walk), путём (path) и циклом (cycle)?

Accepted Answer

Маршрут может повторять вершины/рёбра. Путь — это маршрут без повторяющихся вершин. Цикл — это замкнутый путь (начало = конец) без повторяющихся вершин, кроме первой/последней.

Question 3

Что означает, что граф планарный, и какова формула Эйлера для связных планарных графов?

Accepted Answer

Планарный означает, что его можно изобразить на плоскости без пересечений рёбер (кроме пересечений в вершинах). Для связного планарного вложения $$V-E+F=2,$$ где $F$ — число граней (включая внешнюю грань).

Флеш-карточки по основам теории графов

Освойте Математику с ИИ

Учебные Ресурсы

Нам доверяют