Loading AI tools
З Вікіпедії, вільної енциклопедії
У теорії графів двогранний граф[1] або напіврегулярний двочастковий граф[2] є двочастковим графом для якого кожні дві вершини на одній і тій же стороні даного двонаправленого розділу мають однаковий степінь. Якщо вершин в мають степінь , а вершини в степеня , тоді граф називається -двогранним.
Види графів за їхніми автоморфізмами | ||||
відстанево-транзитивний | сильно регулярний | |||
симетричний (дуго-транзитивний) | t-транзитивний, t ≥ 2 | |||
(якщо зв'язний) | ||||
вершинно- та реберно-транзитивний[en] | реберно-транзитивний і регулярний | реберно-транзитивний | ||
вершинно-транзитивний | регулярний | |||
граф Келі | кососиметричний[en] | асиметричний |
Кожен повний двочастковий граф є -двогранним[3]. Ромбододекаедр є ще одним прикладом; він є (3,4)-двогранним графом[4] .
-двогранний граф має задовольняти рівняння . Це випливає з простого аргументу подвійного підрахунку[en]: кількість кінців ребер з дорівнює , кількість кінців ребер в дорівнює , і кожне ребро додає однакову кількість в обидва числа.
Кожен регулярний двочастковий граф також є двогранним. Кожен реберно-транзитивний граф (забороняються графи з ізольованими вершинами), який не є також вершинно-транзитивним, повинен бути двогранним[3]. Зокрема, кожен реберно-транзитивний граф є або регулярним, або бірегулярним (двогранним).
Графи Леві геометричних конфігурацій є двогранними; двогранний граф — це граф Леві (абстрактної) конфігурації тоді й тільки тоді, коли його обхват становить не менше шести[5].
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.