Teljes bipartit gráf

A teljes kétrészes gráf ( biklik ) a kétrészes gráf egy speciális típusa, amelyben az első rész bármely csúcsa kapcsolódik a csúcsok második részének összes csúcsához.

Definíció

A teljes bipartit gráf egy olyan kétrészes gráf, amely bármely két csúcsra és , egy él a -ben . Egy teljes kétrészes gráf méretű részekkel és jelölése . $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}}$

Példák

A grafikonokat csillagoknak nevezik , minden teljes kétoldalú gráf, amely fák , csillag. $K_{{1,k}}$
A gráfot karmoknak nevezik , és karmok nélküli gráfok meghatározására szolgál . $K_{{1,3}}$
A grafikont néha "közösségi gráfnak" is nevezik, az elnevezés a klasszikus " házak és kutak " problémára nyúlik vissza, modern értelmezésben a "kommunális" megfogalmazással (köss össze három házat vízre, villanyra és gázra anélkül, hogy átlépnék a vonalakat repülőgép); a probléma a gráf nem síkszerűsége miatt megoldhatatlan . $K_{{3,3}}$ $K_{{3,3}}$

Tulajdonságok

Az a probléma, hogy egy adott bipartit gráfhoz egy adott paraméterrel rendelkező teljes kétrészes részgráfot találjunk, NP-teljes . $K_{{n,n}}$ $n$
Egy síkgráf nem tartalmazhat mellék gráfot . Egy külső síkbeli gráf nem tartalmazhat minorként (ez nem elégséges feltétele a síkságnak és a külső síkosságnak, de szükséges). Ezzel szemben minden nem síkbeli gráf tartalmazza a vagy a teljes gráfot mellékként ( Ponrjagin-Kuratovszkij tétel ). $K_{{3,3}}$ $K_{{3,2}}$ $K_{{3,3}}$ $K_{5}$
A teljes kétrészes gráfok Moore - gráfok és -cellák . $K_{{n,n}}$ $(n,4)$
A teljes kétrészes gráfok a Turan-gráfok . $K_{{n,n}}$ $K_{{n,n+1}}$
A teljes kétrészes gráfnak van csúcsborító mérete és élborító mérete . $K_{{m,n}}$ $\perc(p,n)$ $\max(m,n)$
Egy teljes kétrészes gráf maximális független méretkészlettel rendelkezik . $K_{{m,n}}$ $\max(m,n)$
Egy teljes kétrészes gráf szomszédsági mátrixának sajátértékei vannak , és , illetve multiplicitásokkal . $K_{{m,n}}$ ${\sqrt{nm))$ $-{\sqrt{nm))$ $0$ $egy$ $egy$ $n+m-2$
A teljes kétrészes gráf Laplace-mátrixának sajátértékei , , , multiplicitásokkal , , és rendre. $K_{{m,n}}$ $n+m$ $n$ $m$ $0$ $egy$ $m-1$ $n-1$ $egy$
Egy teljes kétrészes gráfban vannak feszítőfák . $K_{{m,n}}$ $m^{{n-1}}\cdot n^{{m-1}}$
A teljes kétrészes gráf mérete maximálisan illeszkedik . $K_{{m,n}}$ $\perc(p,n)$
Egy teljes kétrészes gráf megfelelő élszínezéssel rendelkezik, amely megfelel a latin négyzetnek . $K_{{n,n}}$ $n$

Az utolsó két eredmény a Hall-tétel következménye , amelyet egy -reguláris bipartit gráfra alkalmaztunk. $k$

Lásd még

Irodalom

John Adrian Bondy, USR Murty. Gráfelmélet alkalmazásokkal. - Észak-Hollandia, 1976. - 5. o . — ISBN 0-444-19451-7 . Az eredetiből archiválva : 2010. április 13.
Reinhard Diestel. Gráfelmélet // 3. - Springer , 2005. - S. 17 . — ISBN 3-540-26182-6 .