1- Czy są jakieś szczególne właściwości macierzy przylegania, gdy wykres jest płaski?
2- Czy jest coś specjalnego do obliczania stałej macierzy przylegania, gdy wykres jest płaski?
graph-theory
co.combinatorics
permanent
marjoonjan
źródło
źródło
Odpowiedzi:
Obliczanie wyznaczników i stałych grafów płaskich jest tak trudne, jak obliczanie ich na grafach ogólnych. Są kompletne odpowiednio dla GapL i #P . Zobacz ten artykuł Datty, Kulkarni, Limaye, Mahajan, aby uzyskać więcej informacji.
źródło
Jest to bardziej właściwość macierzy padania niż macierzy przylegania, ale jedną ważną właściwością grafów płaskich jest to, że są to dokładnie wykresy, których matroid graficzny jest podwójny z innym matroidem graficznym. Związek z macierzami padania polega na tym, że matroid graficzny opisuje zestawy niezależnych kolumn w macierzy.
źródło
Istnieje właściwość macierzy odległości (a nie macierzy przylegania) ograniczonych grafów płaskich, która może być interesująca, właściwość Monge . Właściwość Monge (z powodu Gaspard Monge) dla grafów płaskich zasadniczo oznacza, że niektóre najkrótsze ścieżki nie mogą się przeciąć. Zobacz Wikipedia: Monge Array, aby uzyskać formalny opis właściwości Monge. Djidjev (WG 1996) ( artykuł na stronie internetowej Dżidżiwa ) oraz Fakcharoenphol i Rao (FOCS 2001) ( wideo ) pokazują, jak wykorzystać właściwości nieprzekraczania w algorytmach najkrótszej ścieżki.
źródło
Nie jestem pewien, jakiego rodzaju właściwości szukasz, ale promień spektralny grafów płaskich jest jedną z takich wielkości (maksymalna wartość bezwzględna wartości własnej macierzy sąsiedniej). Zobacz na przykład ten artykuł .
źródło
Chociaż nie jest to bezpośrednio związane z twoim pytaniem, możesz przyjrzeć się pracy nad sekwencjami stopni grafów płaskich. Nie są znane charakterystyki, kiedy sekwencją stopni jest sekwencja stopni na wykresie planarnym. Istnieje jednak wiele interesujących artykułów na takie tematy, w tym:
http://www.jstor.org/pss/2100346
źródło