Флешкартки з основ теорії графів

Question 1

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

Accepted Answer

Граф — це впорядкована пара $G=(V,E)$, де $V$ — множина вершин (вузлів), а $E$ — множина ребер, кожне з яких з’єднує дві вершини (в неорієнтованому графі ребро є невпорядкованою парою $\{u,v\}$).

Question 2

У чому різниця між маршрутом, шляхом і циклом?

Accepted Answer

Маршрут може повторювати вершини/ребра. Шлях — це маршрут без повторення вершин. Цикл — це замкнений шлях (початок = кінець) без повторення вершин, крім першої/останньої.

Question 3

Що означає, що граф є планарним, і яка формула Ейлера для зв’язних планарних графів?

Accepted Answer

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

Флешкартки з основ теорії графів

Опануйте Математику з ШІ

Навчальні Ресурси

Довіра та Визнання