Páros gráf fele
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.[1] 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.[2]
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.[3]
Fordítás[szerkesztés]
- Ez a szócikk részben vagy egészben a Bipartite half című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek[szerkesztés]
- ↑ Wilson, Robin J. (2004), Topics in Algebraic Graph Theory, vol. 102, Encyclopedia of Mathematics and its Applications, Cambridge University Press, p. 188, ISBN 9780521801973, <https://books.google.com/books?hl=en&lr=&id=z2K26gZLC1MC&oi=fnd&pg=PA188>.
- ↑ Chihara, Laura & Stanton, Dennis (1986), "Association schemes and quadratic transformations for orthogonal polynomials", Graphs and Combinatorics 2 (2): 101–112, DOI 10.1007/BF01788084.
- ↑ Chen, Zhi-Zhong; Grigni, Michelangelo & Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM 49 (2): 127–138, DOI 10.1145/506147.506148.
