Сірниковий граф
У теорії графів сірниковим графом називають граф, який можливо намалювати на площині таким чином, що всі його ребра являють собою відрізки прямої завдовжки одиниця, і ребра не перетинаються. Таким чином, цей граф має проєкцію на площину одночасно у вигляді графа одиничних відстаней і планарного графа.
Говорячи неформально, сірниковий граф можна викласти на плоскій поверхні сірниками, що не перетинаються, звідки й назва[1].
Регулярні сірникові графи ред.
Багато досліджень сірникових графів стосуються регулярних графів, у яких кожна вершина має однакову кількість сусідів. Це число називається ступенем графа.
Відомо, що існують сірникові графи всіх ступенів аж до четвертого. Повні графи з однією, двома і трьома вершинами (окрема вершина, ребро і трикутник) є сірниковими графами, 0-, 1- і 2-регулярними відповідно. Найменший 3-регулярний сірниковий граф утворюється двома копіями ромбів, розміщених таким чином, що відповідні вершини розташовані на одиничній відстані. Його подвійне двочасткове покриття (bipartite double cover) — це граф 8-кутної призми з перетинами[1].
Примітки ред.
- ↑ а б Weisstein, Eric W. MatchstickGraph(англ.) на сайті Wolfram MathWorld.