Direkte produkt af grafer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. februar 2021; checks kræver 2 redigeringer .

Et kartesisk eller direkte produkt [1] G H af graferne G og H er en graf sådan, at

Det kartesiske produkt kan genkendes effektivt i lineær tid [2] . Operationen er kommutativ som en operation på grafisomorfi - klasser , og mere strengt er graferne G H og H G naturligt isomorfe , men operationen er ikke kommutativ som en operation på mærkede grafer. Operationen er også associativ , da graferne ( F G ) H og F ( GH ) er naturligt isomorfe.

Notationen G × H bruges lejlighedsvis også til det kartesiske produkt af grafer, men oftere bruges det til en anden konstruktion kendt som tensorproduktet af grafer . Det firkantede symbol er mere almindeligt brugt og er utvetydigt for det kartesiske produkt af grafer. Den viser visuelt de fire kanter, der stammer fra det kartesiske produkt af to kanter [3]

Eksempler

Således er det kartesiske produkt af to hyperkubegrafer en anden hyperkube - Q i Q j =Q i+j .

Egenskaber

Hvis en forbundet graf er et kartesisk produkt, kan den opdeles unikt til et produkt af primfaktorer, grafer, der ikke kan dekomponeres til et produkt af grafer [4] [5] . Imidlertid beskrev Imrich og Klavzhar [6] en afbrudt graf, som kan repræsenteres på to forskellige måder som et kartesisk produkt af simple grafer:

(K 1 + K 2 + K 2 2 ) (K 1 + K 2 3 )=(K 1 + K 2 2 + K 2 4 ) (K 1 + K 2 ),

hvor plustegnet betyder en usammenhængende forening, og overskriften betyder et multipelt kartesisk produkt.

Et kartesisk produkt er en vertex-transitiv graf, hvis og kun hvis hver af dens faktorer er vertex-transitiv [7] .

Et kartesisk produkt er todelt , hvis og kun hvis hver af dets faktorer er todelt. Mere generelt opfylder det kromatiske tal for et kartesisk produkt ligningen

χ(GH )=max {χ(G), χ(H)} [8] .

Hedetniemis formodning angiver en relateret lighed for tensorproduktet af grafer . Uafhængighedstallet for kartesiske produkter er ikke let at beregne, men som Vizing [5] viste , tilfredsstiller uafhængighedstallet ulighederne

α( G )α( H ) + min{|V( G )|-α( G ),|V( H )|-α( H )} ≤ α( GH ) ≤ min{α( G ) | V ( H )|, a( H )|V( G )|}.

Vizings formodning siger, at dominanstallet for et kartesisk produkt tilfredsstiller uligheden

γ( GH ) ≥ γ( G )γ( H ) .

Algebraisk grafteori

Algebraisk grafteori kan bruges til at analysere det kartesiske produkt af grafer. Hvis en graf har knudepunkter og en tilstødende matrix , og en graf har knudepunkter og en tilstødende matrix , så er nabomatrixen af ​​det kartesiske produkt af to grafer givet ved

,

hvor betegner Kronecker-produktet af matricer, og betegner identitetsmatrixen [9] .

Historie

Ifølge Imrich og Klavzhar [6] blev kartesiske produkter af grafer defineret i 1912 af Whitehead og Russell . Produktet af grafer blev gentagne gange genopdaget senere, især af Gert Sabidoussi [4] .

Noter

  1. ↑ Vizing brugte udtrykket "kartesisk produkt", i artiklen " Direkte produkt " kaldes det samme produkt direkte.
  2. ↑ ( Imrich og Peterin 2007 ). For tidligere polynomielle tidsalgoritmer, se Feigenbaum, Hershberger , Schäffer 1985 og Aurenhammer, Hagauer, Imrich 1992 .
  3. ↑ Hahn, Sabidussi, 1997 .
  4. ↑ 1 2 Sabidussi, 1960 .
  5. ↑ 1 2 Vizing, 1963 .
  6. ↑ 1 2 Imrich, Klavžar, 2000 .
  7. ↑ Imrich, Klavžar, 2000 , s. Sætning 4.19.
  8. ↑ Sabidussi, 1957 .
  9. ↑ Kaveh, Rahami, 2005 .

Litteratur

Links