Сірниковий граф

У теорії графів сірниковим графом називають граф, який можливо намалювати на площині таким чином, що всі його ребра являють собою відрізки прямої завдовжки одиниця, і ребра не перетинаються. Таким чином, цей граф має проєкцію на площину одночасно у вигляді графа одиничних відстаней і планарного графа.

Граф Харборта

Говорячи неформально, сірниковий граф можна викласти на плоскій поверхні сірниками, що не перетинаються, звідки й назва.

Регулярні сірникові графи

Багато досліджень сірникових графів стосуються регулярних графів, у яких кожна вершина має однакову кількість сусідів. Це число називається графа.

Відомо, що існують сірникові графи всіх ступенів аж до четвертого. Повні графи з однією, двома і трьома вершинами (окрема вершина, ребро і трикутник) є сірниковими графами, 0-, 1- і 2-регулярними відповідно. Найменший 3-регулярний сірниковий граф утворюється двома копіями ромбів, розміщених таким чином, що відповідні вершини розташовані на одиничній відстані. Його подвійне двочасткове покриття (bipartite double cover) — це граф 8-кутної призми з перетинами.

Примітки

1. Weisstein, Eric W. MatchstickGraph(англ.) на сайті Wolfram MathWorld.