Дерево і плоскі графи
Впізнавай дерева, рахуй ребра дерева й остовне дерево, рахуй грані плоского графа за формулою Ейлера.
📖 Почніть тут: читайте кроки «Уроку» по порядку (1, 2, 3 …) і відповідайте на кожне запитання. Потім переходьте до «Практики».
- Росія: 8 клас
Поради для дорослих
В українській програмі цієї теми немає, це розширення. Деревом називають зв'язний граф без циклів. Властивості дерева: між будь-якими двома вершинами рівно один ланцюг; у дерева з n вершинами рівно n − 1 ребро; у дереві з більше ніж однією вершиною є вершина степеня 1 (листок). Дерева описують родинні дерева, змісти книжок, схеми турнірів з вибуванням.
Остовне дерево зв'язного графа — його частина, що містить усі вершини і є деревом. Щоб отримати остов графа з В вершин і Р ребер, треба прибрати Р − (В − 1) ребер (по одному з кожного циклу).
Граф називають плоским, якщо його можна намалювати на площині без перетину ребер. Для зв'язного плоского графа виконується формула Ейлера: В − Р + Г = 2, де В — кількість вершин, Р — кількість ребер, Г — кількість граней, разом із зовнішньою. Ця формула належить до матеріалу підвищеного рівня.