Що таке рівняння для плоского графіка?
Рівняння v−e+f=2 v − e + f = 2 називається формулою Ейлера для плоских графів.
Теорема Ханані-Тутте стверджує, що граф є плоским тоді і тільки тоді, коли він має малюнок, на якому кожна незалежна пара ребер перетинається парну кількість разів; його можна використовувати для характеристики планарних графів за допомогою системи рівнянь за модулем 2.
Формула Ейлера працює лише з плоскими мережами, і це не виглядає плоским – краї перетинаються! Але навіть незважаючи на те, що це не плоске представлення, ми можемо перевірити, чи воно є, перевіривши, чи формула вірна.
Планарне креслення графіка G = (V,E) складається з відображення з вершин на площину, z : V → IR2, разом із внутрішніми непересічними кривими для кожного ребра. Крива для ребра (a, b) починається в z(a), закінчується в z(b), ніколи не перетинає саму себе, і її внутрішність не перетинає криву для будь-якого іншого ребра.
Формула Ейлера V − E + F = 2 виконується для будь-якого графа, який має ейлерів тур. Перш ніж довести це, ми використаємо це, щоб навести коротку теорему 2.1. Цей доказ знайшла Стефані Метью, коли вона була студенткою другого курсу інженерного факультету Х’юстонського університету. E(G0)=2E(G) і F(G0) = F(G) + E(G).
Рівняння v−e+f=2 v − e + f = 2 називається формулою Ейлера для плоских графів.