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 .








Példák
- A grafikonokat csillagoknak nevezik , minden teljes kétoldalú gráf, amely fák , csillag.

- A gráfot karmoknak nevezik , és karmok nélküli gráfok meghatározására szolgál .

- 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 .


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 .

- 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 ).



- A teljes kétrészes gráfok Moore - gráfok és -cellák .


- A teljes kétrészes gráfok a Turan-gráfok .


- A teljes kétrészes gráfnak van csúcsborító mérete és élborító mérete .



- Egy teljes kétrészes gráf maximális független méretkészlettel rendelkezik .


- Egy teljes kétrészes gráf szomszédsági mátrixának sajátértékei vannak , és , illetve multiplicitásokkal .







- A teljes kétrészes gráf Laplace-mátrixának sajátértékei , , , multiplicitásokkal , , és rendre.









- Egy teljes kétrészes gráfban vannak feszítőfák .

- A teljes kétrészes gráf mérete maximálisan illeszkedik .


- Egy teljes kétrészes gráf megfelelő élszínezéssel rendelkezik, amely megfelel a latin négyzetnek .


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

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 .