![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/langhu-640px-Simple-bipartite-graph.svg.png&w=640&q=50)
Páros gráf
matematikai fogalom a gráfelméletben / From Wikipedia, the free encyclopedia
Páros gráfnak, kétrészes gráfnak vagy páros körüljárású gráfnak nevezünk egy gráfot, ha
csúcsainak halmazát fel tudjuk úgy osztani egy
és
halmazra, hogy az összes
-beli élre teljesül, hogy az egyik végpontja
-ban van, a másik pedig
-ben. Egy
páros gráfot következőképpen jelölünk:
.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/320px-Simple-bipartite-graph.svg.png)
Kézenfekvő példa a következő: legyenek a gráf csúcsai egy sakktábla mezői, két csúcs közé akkor vegyünk fel élt, ha egyik a másikról üthető huszárral. Ekkor A-ba a világos, B-be a sötét mezőket helyezve páros gráfot kapunk, hiszen bármely mezőről csak eltérő színű mező üthető.
Páros gráf minden részgráfja is páros. Minden fa páros gráf.
Teljes páros gráfnak nevezünk egy olyan páros gráfot, melyben minden -beli pont össze van kötve minden
-beli ponttal. Jelölés:
, ahol
és
.