| dbo:abstract
|
- 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 elvesztése 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 .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. (hu)
- 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 elvesztése 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 .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. (hu)
|
