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

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

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

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

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

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

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

Примітки
  1. Weisstein, Eric W. MatchstickGraph(англ.) на сайті Wolfram MathWorld.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.