Пълна двустранна графика

двустранна

Пълният двустранен граф(bi-clique) е специален вид двустранен граф, в който всеки връх от първата част е свързан с всички върхове от втората част от върховете.

Съдържание

  • Графики K1, k > се наричат ​​звезди, всички пълни двустранни дървовидни графи са звезди.
  • Графика K1, 3 > се нарича нокът и се използва за дефиниране на графи без нокти.
  • Графика K3, 3 > понякога наричана „обща графика“, името се връща към класическия проблем „къщи и кладенци“, в съвременна интерпретация, използвайки формулировката „обща“ (свържете три къщи към водоснабдяване, електричество и газ без пресичане на линии в равнина); проблемът е неразрешим поради непланарността на графиката K 3 , 3 > .
  • Проблемът за намиране на пълен двуделен подграф K m , n>NP-пълен за даден двуделен граф.
  • Една равнинна графика не може да съдържа K3, 3 > като минор на графиката. Една външна равнинна графика не може да съдържа K 3 , 2>gt; като минор (Това не е достатъчно условие за планарност и външна планарност, но е необходимо). Обратно, всяка неравнинна графика съдържа или K3, 3 > , или пълната графика K5>gt; като минор (теорема на Куратовски [en]).
  • Пълни двуделни графи K n , n > са графики на Мур и са (n, 4)-клетки.
  • Пълни двуделни графи K n , n > и Kn, n+1>gt; са графове на Туран.
  • Пълна двустранна графа Km, n>gt; има размер на покритието на върха от min (m, n) и размер на покритието на ръба от max (m, n).
  • Пълна двустранна графа Km, n>gt; има максимален независим набор от размер max (m, n).
  • Матрицата на съседство на пълния двустранен граф K m, n>gt; има своя собственаn стойности >> , −n m >> и 0 с кратности съответно 1, 1 и n + m − 2.
  • Матрицата на Лаплас на пълния двустранен граф Km, n > има собствени стойности n + m , n , m , 0 с кратности съответно 1 , m − 1 , n − 1 и 1.
  • Пълна двустранна графа Km, n>gt; има m n − 1 ⋅ n m − 1 \cdot n^> обхващащи дървета.
  • Пълна двустранна графа Km, n>gt; има максимално съвпадение на размер min ( m , n ) .
  • Пълна двустранна графа K n , n>gt; има подходящо оцветяване на n-ръба, съответстващо на латинския квадрат.

Последните два резултата са следствие от теоремата на Хол, приложена към k -правилен двуделен граф.