Produsul lexicografic al graficelor

Produsul lexicografic sau suprapunerea graficelor este construcția unui grafic dat doi. Dacă legăturile de margine din două grafice sunt relații de ordine , atunci legătura de margine din produsul lor lexicografic este ordinea lexicografică corespunzătoare - de unde și numele.

Lucrarea lexicografică a fost studiată pentru prima dată de Felix Hausdorff [1] .

Definiție

$G\cdot H$ graficele G și H este un grafic astfel încât

Mulțimea vârfurilor graficului este ; adică produsul direct al mulţimilor de vârfuri ale graficelor şi . $G\cdot H$ $V(G)\time V(H)$ $G$ $H$
Orice două vârfuri ( u , v ) și ( x , y ) sunt adiacente în dacă și numai dacă fie u este adiacent cu x în G sau și v este adiacent cu y în H . $G\cdot H$ $u=x$

Proprietăți

Produsul lexicografic nu este în general comutativ : . Cu toate acestea, satisface legea distributivă a uniunii disjunctive : . $G\cdot H\neq H\cdot G$ $(A+B)\cdot C=A\cdot C+B\cdot C$

Pentru completări se efectuează următoarele: . $\mathrm {C} (G\cdot H)=\mathrm {C} (G)\cdot \mathrm {C} (H)$

Numărul de independență al unui produs lexicografic poate fi ușor calculat din factorii săi [2] : $\alpha (G\cdot H)=\alpha (G)\alpha (H)$ .

Numărul clică al unui produs lexicografic este multiplicativ: $\omega (G\cdot H)=\omega (G)\omega (H)$ .

Numărul cromatic al produsului lexicografic este egal cu numărul cromatic al graficului G pentru b , egal cu numărul cromatic al lui H : $\chi (G\cdot H)=\chi _{b}(G)$ , unde . $b=\chi (H)$

Produsul lexicografic a două grafice este un grafic perfect dacă și numai dacă ambii factori sunt perfecți [3] .

Sarcina de a recunoaște dacă un graf este un produs lexicografic este echivalentă ca complexitate cu problema izomorfismului grafului . [patru]

Note

↑ Felix Hausdorff . Grundzuge der Mengenlehre. - Leipzig, 1914. Traducere: F. Hausdorff. Teoria multimilor. - Moscova, Leningrad: Editura Unită științifică și tehnică a URSS NKTP. Ediția principală a literaturii tehnice și teoretice, 1937.
↑ Geller D., Stahl S. Numărul cromatic și alte funcții ale produsului lexicografic // Journal of Combinatorial Theory . - 1975. - T. 19 . — S. 87–95 . - doi : 10.1016/0095-8956(75)90076-3 .
↑ Ravindra G., Parthasarathy KR Perfect product graphs // Discrete Mathematics. - 1977. - T. 20 , nr. 2 . — S. 177–186 . - doi : 10.1016/0012-365X(77)90056-5 .
↑ Feigenbaum J., Schäffer AA Recunoașterea graficelor compozite este echivalentă cu testarea izomorfismului graficului // SIAM Journal on Computing . - 1986. - T. 15 , nr. 2 . — S. 619–627 . - doi : 10.1137/0215045 .

Literatură

Wilfried Imrich, Sandi Klavzar. Grafice de produs: Structură și recunoaștere. - Wiley, 2000. - ISBN 0-471-37039-8 .

Link -uri

Weisstein, Eric W. Graph Lexicographic Product (engleză) pe site-ul Wolfram MathWorld .