У теорії графів сірниковим графом називають граф, який можливо намалювати на площині таким чином, що всі його ребра являють собою відрізки прямої завдовжки одиниця, і ребра не перетинаються. Таким чином, цей граф має проєкцію на площину одночасно у вигляді графа одиничних відстаней і планарного графа.
Говорячи неформально, сірниковий граф можна викласти на плоскій поверхні сірниками, що не перетинаються, звідки й назва.
Регулярні сірникові графи
Багато досліджень сірникових графів стосуються регулярних графів, у яких кожна вершина має однакову кількість сусідів. Це число називається графа.
Відомо, що існують сірникові графи всіх ступенів аж до четвертого. Повні графи з однією, двома і трьома вершинами (окрема вершина, ребро і трикутник) є сірниковими графами, 0-, 1- і 2-регулярними відповідно. Найменший 3-регулярний сірниковий граф утворюється двома копіями ромбів, розміщених таким чином, що відповідні вершини розташовані на одиничній відстані. Його подвійне двочасткове покриття (bipartite double cover) — це граф 8-кутної призми з перетинами.
Примітки
- Weisstein, Eric W. MatchstickGraph(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi grafiv sirnikovim grafom nazivayut graf yakij mozhlivo namalyuvati na ploshini takim chinom sho vsi jogo rebra yavlyayut soboyu vidrizki pryamoyi zavdovzhki odinicya i rebra ne peretinayutsya Takim chinom cej graf maye proyekciyu na ploshinu odnochasno u viglyadi grafa odinichnih vidstanej i planarnogo grafa Graf Harborta Govoryachi neformalno sirnikovij graf mozhna viklasti na ploskij poverhni sirnikami sho ne peretinayutsya zvidki j nazva Regulyarni sirnikovi grafiBagato doslidzhen sirnikovih grafiv stosuyutsya regulyarnih grafiv u yakih kozhna vershina maye odnakovu kilkist susidiv Ce chislo nazivayetsya grafa Vidomo sho isnuyut sirnikovi grafi vsih stupeniv azh do chetvertogo Povni grafi z odniyeyu dvoma i troma vershinami okrema vershina rebro i trikutnik ye sirnikovimi grafami 0 1 i 2 regulyarnimi vidpovidno Najmenshij 3 regulyarnij sirnikovij graf utvoryuyetsya dvoma kopiyami rombiv rozmishenih takim chinom sho vidpovidni vershini roztashovani na odinichnij vidstani Jogo podvijne dvochastkove pokrittya bipartite double cover ce graf 8 kutnoyi prizmi z peretinami PrimitkiWeisstein Eric W MatchstickGraph angl na sajti Wolfram MathWorld