Wykres krzyżowy
| Wykres krzyżowy | |
|
Przedstawienie wykresu krzyżowego. | |
| Liczba wierzchołków | 6 |
|---|---|
| Liczba krawędzi | 5 |
| Dystrybucja stopni | 1 (4 wierzchołki) 2 (1 wierzchołek) 4 (1 wierzchołek) |
| Promień | 2 |
| Średnica | 3 |
| Siatka | ∞ |
| Automorfizmy | 6 |
| Liczba chromatyczna | 2 |
| Indeks chromatyczny | 4 |
| Nieruchomości |
Dwuczęściowy Planar Jednostka odległości Wał |
Przekroju wykres jest w teorii wykres , wykres z 6 wierzchołków i 5 krawędzie.
Wykres krzyżowy nazw jest używany w klasyfikacji ISGCI (system informacji o klasach grafów i ich włączeniach).
Nieruchomości
Właściwości ogólne
Średnica przekroju wykresu maksymalna mimośrodowość wierzchołków, wynosi 3, jego promień minimalny mimośród wierzchołków, wynosi 2. Nie ma cykl jego oczka jest więc nieskończona.
Jest to graf acykliczny i połączony , czyli drzewo . Jest to zatem 1- połączony wierzchołek i 1- połączona krawędź , to znaczy jest połączony i aby go rozłączyć, wystarczy pozbawić go wierzchołka lub krawędzi.
Ponieważ wykres krzyżowy jest drzewem, można go narysować na płaszczyźnie bez przecinania się żadnej z jego krawędzi. Dlatego jest płaska . Jest to również wykres jednostek odległości : można go uzyskać ze zbioru punktów na płaszczyźnie euklidesowej, łącząc krawędzią wszystkie pary punktów w odległości 1.
Kolorowanie
Liczba chromatyczna wykresu krzyżowego wynosi 2. To znaczy, że można go pokolorować dwoma kolorami, tak aby dwa wierzchołki połączone krawędzią miały zawsze różne kolory. Ta liczba jest minimalna.
Chromatycznej wskaźnik przekroju wykresie oznacza 4. Jest to zatem 4 barwienia krawędzi grafu, tak że dwie krawędzie incydent ten sam wierzchołek zawsze są w różnych kolorach. Ta liczba jest minimalna.
Można policzyć różne zabarwienia wykresu krzyżowego. Daje to funkcję zależną od liczby dozwolonych kolorów. Jest to funkcja wielomianowa, a związany z nią wielomian nazywany jest wielomianem chromatycznym . Ten wielomianu stopnia 6 przyznaje korzenie wszystkich dodatnich liczb całkowitych lub zero ściśle mniej niż 2. Jest ona równa: .
Właściwości algebraiczne
Grupa automorfizmów wykresu krzyżowego to grupa rzędu 6 izomorficzna z grupą symetryczną S 3 . Automorfizmy odpowiadają wszystkim możliwym permutacjom trzech wierzchołków stopnia 1, które są połączone z unikalnym wierzchołkiem stopnia 4.
Wielomian charakterystyczny z matrycy przylegania przekroju wykresu jest: . Wykres krzyżowy jest jednoznacznie określony przez widmo wykresu , zbiór wartości własnych macierzy sąsiedztwa .
Zobacz też
Linki wewnętrzne
Linki zewnętrzne
- (en) Eric W. Weisstein , Cross Graph ( MathWorld )
Bibliografia
- (in) ISGCI (System informacji o włączeniach klas grafów i ich) Lista małych wykresów .