Jumătate bipartită
În teoria graficelor , jumătatea sau jumătatea pătrată a unui grafic bipartit este un grafic al cărui set de vârfuri este mulțimea (unul dintre cele două seturi de vârfuri ale bipartiției) și în care există o margine între și dacă sunt la distanța două în , cu alte cuvinte, dacă există un vârf astfel încât să existe o margine între și și între și în grafic . Într-o notație mai compactă, jumătatea bipartită este , unde exponentul indică pătratul graficului, iar setul dintre paranteze pătrate denotă subgraful indus de .
G=(U,V,E){\ displaystyle G = (U, V, E)}H=(U,F){\ displaystyle H = (U, F)}U{\ displaystyle U}(tu,tu′){\ displaystyle (u, u ')}tu{\ displaystyle u}tu′{\ displaystyle u '}G{\ displaystyle G}v∈V{\ displaystyle v \ in V}tu{\ displaystyle u}v{\ displaystyle v}tu′{\ displaystyle u '}v{\ displaystyle v}G{\ displaystyle G}H=G2(U){\ displaystyle H = G ^ {2} (U)}U{\ displaystyle U}
De exemplu, jumătatea pătratului graficului bipartit complet este graficul complet K n, iar jumătatea bipartită a hipercubului este jumătatea hipercubului . Când este un grafic cu distanță regulată , cele două jumătăți ale sale bipartite sunt grafice cu distanță regulată.
Knu,nu{\ displaystyle K_ {n, n}} Knu{\ displaystyle K_ {n}}G{\ displaystyle G}
De exemplu, jumătate din graficul Foster bipartit este un grafic al setului finit al graficului distanță-regulat de gradul 6 grafice liniare local (în)
„Graficele hărții”, care sunt graficele de intersecție ale regiunilor conectate simplu ale planului interioarelor disjuncte, sunt exact jumătățile bipartite ale graficelor plane
Articol asociat
-
Bipartisan cu dublă acoperire (ro)
Note și referințe
-
Robin J. Wilson , Topics in Algebraic Graph Theory , vol. 102, Cambridge University Press, col. "Enciclopedia matematicii și aplicațiile sale",2004( ISBN 9780521801973 , citit online ) , p. 188.
-
Laura Chihara și Dennis Stanton , „ Scheme de asociere și transformări pătratice pentru polinoame ortogonale ”, Graphs and Combinatorics , vol. 2 n o 21986, p. 101–112 ( DOI 10.1007 / BF01788084 , Recenzii matematice 932118 ).
-
Akira Hiraki , Kazumasa Nomura și Hiroshi Suzuki , „ Distanță-grafice regulate ale valenței 6 șila1=1{\ displaystyle a_ {1} = 1} ”, Journal of Algebraic Combinatorics (en) , vol. 11, n o 22000, p. 101–134 ( DOI 10.1023 / A: 1008776031839 , Recenzii matematice 1761910 )
-
Zhi-Zhong Chen , Michelangelo Grigni și Christos H. Papadimitriou , „ Hărți grafice ”, Jurnalul ACM , vol. 49, n o 22002, p. 127–138 ( DOI 10.1145 / 506147.506148 , Math Reviews 2147819 , arXiv cs / 9910013 ).
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">