Komplett tvådelad graf

En komplett tvådelad graf ( biklik ) är en speciell typ av tvådelad graf där varje hörn av den första delen är kopplad till alla hörn i den andra delen av hörn.

Definition

En komplett tvådelad graf är en tvådelad graf så att för alla två hörn och , är en kant i . En komplett tvådelad graf med delar av storlek och betecknas som . $G:=(V_{1}+V_{2},E)$ $v_{1}\in V_{1}$ $v_{2}\in V_{2}$ $(v_{1},v_{2})$ $G$ $|V_{1}|=m$ $|V_{2}|=n$ $K_{{m,n}}$

Exempel

Grafer kallas stjärnor , alla kompletta tvådelade grafer som är träd är stjärnor. $K_{{1,k}}$
Grafen kallas en klo och används för att definiera grafer utan klor . $K_{{1,3}}$
Grafen kallas ibland "gemensam graf", namnet går tillbaka till det klassiska " hus och brunnar "-problemet, i en modern tolkning som använder "gemensamma" formuleringen (anslut tre hus till vatten, el och gas utan att korsa linjer på plan); problemet är olösligt på grund av att grafen inte är plan . $K_{{3,3}}$ $K_{{3,3}}$

Egenskaper

Problemet med att hitta, för en given tvådelad graf, en komplett tvådelad subgraf med en given parameter är NP-komplett . $K_{{n,n}}$ $n$
En plan graf kan inte innehålla en graf som en mindre . En yttre planär graf kan inte innehålla som en mindre (Detta är inte ett tillräckligt villkor för planaritet och yttre planaritet, utan ett nödvändigt sådant). Omvänt innehåller alla icke-planära grafer antingen , eller hela grafen som en mindre ( Pontryagin-Kuratovskys teorem ). $K_{{3,3}}$ $K_{{3,2}}$ $K_{{3,3}}$ $K_{5}$
Kompletta tvådelade grafer är Moore - grafer och -celler . $K_{{n,n}}$ $(n,4)$
De kompletta tvådelade graferna är Turan- graferna . $K_{{n,n}}$ $K_{{n,n+1}}$
En komplett tvådelad graf har vertextäckstorlek och kanttäckningsstorlek . $K_{{m,n}}$ $\min(m,n)$ $\max(m,n)$
En komplett tvådelad graf har en maximal oberoende uppsättning storlek . $K_{{m,n}}$ $\max(m,n)$
Närliggande matris för en komplett tvådelad graf har egenvärden och med multipliciteter , respektive . $K_{{m,n}}$ ${\sqrt{nm))$ $-{\sqrt{nm))$ $0$ $ett$ $ett$ $n+m-2$
Laplace-matrisen för en komplett tvådelad graf har egenvärden , , , med multipliciteter , , respektive . $K_{{m,n}}$ $n+m$ $n$ $m$ $0$ $ett$ $m-1$ $n-1$ $ett$
En komplett tvådelad graf har spännande träd . $K_{{m,n}}$ $m^{{n-1}}\cdot n^{{m-1}}$
En komplett tvådelad graf har en maximal matchning av storlek . $K_{{m,n}}$ $\min(m,n)$
En komplett tvådelad graf har en lämplig kantfärgning som motsvarar den latinska kvadraten . $K_{{n,n}}$ $n$

De två sista resultaten är en följd av Halls sats tillämpad på en -regelbunden tvådelad graf. $k$

Se även

Litteratur

John Adrian Bondy, USR Murty. Grafteori med applikationer. - Nord-Holland, 1976. - S. 5 . — ISBN 0-444-19451-7 . Arkiverad från originalet den 13 april 2010.
Reinhard Diestel. Grafteori // 3:a. - Springer , 2005. - S. 17 . — ISBN 3-540-26182-6 .