Loading AI tools
матроїдний опис планарних графів З Вікіпедії, вільної енциклопедії
Критерій планарності Вітні — це матроїдний опис планарних графів. Критерій носить ім'я Гасслера Вітні[en][1]. Критерій стверджує, що граф планарний тоді й лише тоді, коли його графовий матроїд[en] є також кографовим (тобто є двоїстим матроїдом[en] іншого графового матроїда).
У термінах чисто теорії графів цей критерій можна сформулювати так:
|
Існують і інші критерії планарності, наприклад, теорема Понтрягіна — Куратовського.
Еквівалентна форма критерію Вітні:
|
Граф, графовий матроїд якого двоїстий графовому матроїду графа , відомий як алгебрично двоїстий граф для графа . Тоді критерій планарності Вітні можна перефразувати так:
|
Якщо граф укладено в топологічну поверхню, таку як площина, так, що будь-яка грань при вкладенні є топологічним диском, то двоїстий граф вкладення визначається як граф (у деяких випадках — мультиграф) , який має вершину для кожної грані вкладення і ребро для кожної пари суміжних граней. Згідно з критерієм Вітні такі умови еквівалентні:
Можна визначити двоїсті графи графа, вкладеного в неплоскі поверхні, такі як тор, але такі двоїсті графи, в загальному випадку, не мають відповідності з розрізами, циклами і кістяковими деревами, яку вимагає критерій Вітні.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.