Grafic bipartit complet

Un graf bipartit complet ( biklik ) este un tip special de graf bipartit în care orice vârf al primei părți este conectat la toate vârfurile celei de-a doua părți a nodurilor.

Definiție

Un graf bipartit complet este un graf bipartit astfel încât pentru oricare două vârfuri și , este o muchie în . Un grafic bipartit complet cu părți de dimensiune și este notat ca . $G:=(V_{1}+V_{2},E)$ $v_{1}\în V_{1}$ $v_{2}\în V_{2}$ $(v_{1},v_{2})$ $G$ $|V_{1}|=m$ $|V_{2}|=n$ $K_{{m,n}}$

Exemple

Graficele sunt numite stele , toate graficele bipartite complete care sunt copaci sunt stele. $K_{{1,k}}$
Graficul se numește gheare și este folosit pentru a defini grafice fără gheare . $K_{{1,3}}$
Graficul este uneori numit „graf comunal”, denumirea se întoarce la problema clasică „ case și fântâni ”, într-o interpretare modernă folosind formularea „comunală” (conectați trei case la apă, electricitate și gaz fără a trece liniile pe avion); problema este de nerezolvat din cauza neplanarității graficului . $K_{{3,3}}$ $K_{{3,3}}$

Proprietăți

Problema găsirii, pentru un graf bipartit dat, a unui subgraf bipartit complet cu un parametru dat este NP-complet . $K_{{n,n}}$ $n$
Un graf plan nu poate conține un graf ca minor . Un grafic exterior planar nu poate conține ca un minor (Acesta nu este o condiție suficientă pentru planaritate și planaritate exterioară, ci una necesară). Dimpotrivă, orice graf neplanar conține fie , fie graful complet ca minor ( teorema Pontryagin-Kuratovsky ). $K_{{3,3}}$ $K_{{3,2}}$ $K_{{3,3}}$ $K_{5}$
Graficele bipartite complete sunt grafice și celule Moore . $K_{{n,n}}$ $(n,4)$
Graficele bipartite complete sunt graficele Turan . $K_{{n,n}}$ $K_{{n,n+1}}$
Un grafic bipartit complet are dimensiunea acoperirii vârfurilor și dimensiunea acoperirii marginii . $K_{{m,n}}$ $\min(m,n)$ $\max(m,n)$
Un graf bipartit complet are un set maxim independent de dimensiuni . $K_{{m,n}}$ $\max(m,n)$
Matricea de adiacență a unui graf bipartit complet are valori proprii și , respectiv , cu multiplicități . $K_{{m,n}}$ ${\sqrt{nm))$ $-{\sqrt{nm))$ $0$ $unu$ $unu$ $n+m-2$
Matricea Laplace a unui graf bipartit complet are valori proprii , , , cu multiplicități , , și respectiv. $K_{{m,n}}$ $n+m$ $n$ $m$ $0$ $unu$ $m-1$ $n-1$ $unu$
Un grafic bipartit complet are copaci spanning . $K_{{m,n}}$ $m^{{n-1}}\cdot n^{{m-1}}$
Un grafic bipartit complet are o potrivire maximă de dimensiune . $K_{{m,n}}$ $\min(m,n)$
Un graf bipartit complet are o colorare adecvată a muchiei corespunzătoare pătratului latin . $K_{{n,n}}$ $n$

Ultimele două rezultate sunt o consecință a teoremei lui Hall aplicată unui graf bipartit regulat. $k$

Vezi și

Literatură

John Adrian Bondy, USR Murty. Teoria grafurilor cu aplicații. - Olanda de Nord, 1976. - P. 5 . — ISBN 0-444-19451-7 . Arhivat din original pe 13 aprilie 2010.
Reinhard Diesel. Teoria grafurilor // a 3-a. - Springer , 2005. - S. 17 . — ISBN 3-540-26182-6 .