Produkt leksykograficzny grafów
W teorii grafów produktem leksykograficznym lub składem (wykresu) G ∙ H grafów G i H jest taki wykres, że
- zbiór wierzchołków G ∙ H jest iloczynem kartezjańskim V(G) × V(H) ; I
- dowolne dwa wierzchołki ( u , v ) i ( x , y ) sąsiadują ze sobą w G ∙ H wtedy i tylko wtedy, gdy albo u sąsiaduje z x w G albo u = x i v sąsiaduje z y w H .
Jeśli relacje krawędziowe dwóch grafów są relacjami porządku , to relacja krawędzi ich iloczynu leksykograficznego jest odpowiednim porządkiem leksykograficznym .
Produkt leksykograficzny został po raz pierwszy zbadany przez Felixa Hausdorffa ( 1914 ). Jak Feigenbaum i Schäffer (1986) , problem rozpoznania, czy graf jest wytworem leksykograficznym, jest równoważny pod względem złożoności problemowi izomorfizmu grafu .
Nieruchomości
Iloczyn leksykograficzny jest na ogół nieprzemienny : G ∙ H ≠ H ∙ G . Jednak spełnia prawo rozdzielności w odniesieniu do związku rozłącznego: ( A + B ) ∙ C = A ∙ C + B ∙ C . Ponadto spełnia tożsamość pod względem dopełnienia : C( G ∙ H ) = C( G ) ∙ do( H. ) . W szczególności iloczyn leksykograficzny dwóch samouzupełniających się grafów jest samouzupełniający się.
Liczba niezależności produktu leksykograficznego może być łatwo obliczona na podstawie liczby jego czynników ( Geller & Stahl 1975 ):
- α ( sol ∙ H. ) = α ( sol ) α ( H. ) .
Numer kliki produktu leksykograficznego jest również multiplikatywny:
- ω( sol ∙ H. ) = ω ( sol ) ω ( H. ) .
Liczba chromatyczna iloczynu leksykograficznego jest równa b -krotnej chromatycznej liczbie G , dla b równej liczbie chromatycznej H :
- χ( sol ∙ H. ) = χ b ( sol ) , gdzie b = χ ( H. ) .
Produkt leksykograficzny dwóch grafów jest grafem doskonałym wtedy i tylko wtedy, gdy oba czynniki są doskonałe ( Ravindra i Parthasarathy 1977 ).
- Feigenbaum, J.; Schäffer, AA (1986), „Rozpoznawanie grafów złożonych jest równoważne testowaniu izomorfizmu grafów”, SIAM Journal on Computing , 15 (2): 619–627, doi : 10.1137/0215045 , MR 0837609 .
- Geller, D.; Stahl, S. (1975), „Liczba chromatyczna i inne funkcje iloczynu leksykograficznego”, Journal of Combinatorial Theory , Seria B, 19 : 87–95, doi : 10.1016/0095-8956 (75) 90076-3 , MR 0392645 .
- Hausdorff, F. (1914), Grundzüge der Mengenlehre , Lipsk
- Imrich, Wilfried; Klavžar, Sandi (2000), Wykresy produktów: struktura i rozpoznawanie , Wiley, ISBN 0-471-37039-8
- Ravindra, G.; Parthasarathy, KR (1977), „Wykresy doskonałych produktów”, Matematyka dyskretna , 20 (2): 177–186, doi : 10.1016/0012-365X(77)90056-5 , hdl : 10338.dmlcz/102469 , MR 0491304 .