páros gráf

Magyar

Kiejtés

IPA: [ ˈpaːroʒɡraːf]

Főnév

(matematika, gráfelmélet) Páros gráfnak, kétrészes gráfnak vagy páros körüljárású gráfnak nevezünk egy $G$ gráfot, ha $G$ csúcsainak halmazát fel tudjuk úgy osztani egy $A$ és $B$ halmazra, hogy az összes $G$ -beli élre teljesül, hogy az egyik végpontja $A$ -ban van, a másik pedig $B$ -ben. Egy $G$ páros gráfot következőképpen jelölünk: $G$ $=$ $(A,B)$ .

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 $A$ -beli pont össze van kötve minden $B$ -beli ponttal. Jelölés: $K_{a,b}$ , ahol $a$ $=$ $|A|$ és $b$ $=$ $|B|$ .