Silny produkt wykresów

W teorii grafów silny iloczyn to sposób łączenia dwóch wykresów w celu uzyskania większego wykresu. Dwa wierzchołki sąsiadują ze sobą w silnym produkcie, gdy pochodzą z par wierzchołków na wykresach czynnikowych, które są albo sąsiadujące, albo identyczne. Silny iloczyn jest jedną z kilku różnych na iloczynach grafów , które badano w teorii grafów. Silny iloczyn dowolnych dwóch grafów można skonstruować jako sumę dwóch innych iloczynów tych samych dwóch grafów, iloczynu kartezjańskiego grafów i iloczynu tensorowego grafów .

Przykładem silnego iloczynu jest wykres króla , wykres ruchów króla szachowego na szachownicy, który można skonstruować jako iloczyn silny wykresów ścieżkowych. Dekompozycje grafów planarnych i powiązanych klas grafów na mocne iloczyny zostały wykorzystane jako główne narzędzie do udowodnienia wielu innych wyników dotyczących tych grafów.

w literaturze termin silny iloczyn , ponieważ był on również używany do określenia iloczynu tensorowego grafów.

Definicja i przykład

Silny iloczyn G H grafów G i H jest grafem takim , że zbiór wierzchołków G H jest iloczynem kartezjańskim V ( G ) × V ( H ) ; i różne wierzchołki ( u , u' ) i ( v , v' ) sąsiadują ze sobą w G H wtedy i tylko wtedy, gdy :

u = v i u' sąsiaduje z v' lub u
, ' = v' i u sąsiaduje z v lub
u sąsiaduje z v a u' sąsiaduje z v' .

Jest to suma iloczynu kartezjańskiego i iloczynu tensorowego .

Na przykład graf króla , graf, którego wierzchołkami są kwadraty szachownicy , a krawędzie reprezentują możliwe ruchy króla szachowego, jest silnym iloczynem dwóch grafów ścieżkowych . Jego krawędzie poziome pochodzą z iloczynu kartezjańskiego, a krawędzie ukośne pochodzą z iloczynu tensorowego tych samych dwóch ścieżek. Razem te dwa rodzaje krawędzi składają się na cały mocny produkt.

Właściwości i zastosowania

Każdy graf planarny jest podgrafem silnego iloczynu ścieżki i grafem o szerokości drzewa co najwyżej sześć. Wynik ten został wykorzystany do udowodnienia, że ​​grafy planarne mają ograniczoną liczbę kolejek , małe grafy uniwersalne i zwięzłe schematy etykietowania sąsiedztwa oraz ograniczoną niepowtarzalną liczbę chromatyczną i wyśrodkowaną liczbę chromatyczną. Tę strukturę produktu można znaleźć w czasie liniowym . Poza grafami planarnymi, rozszerzenia tych wyników zostały udowodnione dla grafów ograniczonego rodzaju , grafów z zabronioną drugorzędną to jest graf wierzchołkowy , grafy o ograniczonych stopniach z dowolnym zabronionym mniejszym i grafy k-planarne .

Liczba klik silnego iloczynu dowolnych dwóch wykresów jest równa iloczynowi liczb klik z dwóch wykresów. Jeśli oba grafy mają ograniczoną szerokość bliźniaczą , a dodatkowo jeden z nich ma ograniczony stopień, to ich iloczyn silny ma również ograniczoną szerokość bliźniaczą.

Potęga liści to wykres utworzony z liści drzewa przez połączenie dwóch liści obok siebie, gdy ich odległość na drzewie jest poniżej pewnego progu. k Jeśli jest liścia drzewa to można znaleźć jako podwykres silnego iloczynu z za - cykl wierzchołków. To osadzanie zostało wykorzystane w algorytmach rozpoznawania potęg liścia.

Silny iloczyn 7-wierzchołkowego cyklu i 4-wierzchołkowego wykresu został zasugerowany jako możliwość 10 . wykres , który poprawiłby znane granice problemu Ziemia-Księżyc ; innym sugerowanym przykładem jest wykres uzyskany przez usunięcie dowolnego wierzchołka z do . W obu przypadkach liczba wierzchołków na tych grafach jest ponad 9 razy większa niż ich największy niezależny zbiór , co oznacza, że ​​ich liczba chromatyczna wynosi co najmniej 10. Nie wiadomo jednak, czy te grafy są dwupłaszczyznowe.