A matematika, azon belül a gráfelmélet területén egy G = (U,V,E) páros gráf páros fele (bipartite half) vagy félnégyzete (half-square) olyan gráf, melynek csúcshalmaza a bipartíció egyik felével egyezik meg (az általánosság megszorítása nélkül ez legyen U) és melyben két U-beli csúcs, ui és uj között akkor húzódik él, ha ui és uj távolsága G-ben éppen 2.. Tömörebb jelöléssel a félnégyzet G2[U], ahol a 2 felső index a gráf négyzetére utal, a szögletes zárójelek pedig feszített részgráfot jelölnek.
Például a Kn,n teljes páros gráf félnégyzete a Kn teljes gráf, a hiperkockagráf páros fele pedig a felezett kockagráf. Amennyiben G távolságreguláris gráf, mindkét félnégyzete távolságreguláris..
A térképgráfok, azaz a sík belsejük tekintetében diszjunkt régióinak metszetgráfjai éppen a páros síkbarajzolható gráfok félnégyzetei..
Fordítás
Jegyzetek
Kategória:Gráfműveletek Kategória:Páros gráfok