Czy istnieją jakieś „graficzne” algebry, które mogą opisać „kształt” wykresów?

Jednym z głównych problemów w wyliczaniu wykresów jest określenie „kształtu” wykresu, np. Klasy izomorfizmu dowolnego konkretnego wykresu. Jestem w pełni świadomy, że każdy wykres może być reprezentowany jako macierz symetryczna. Jednak, aby uzyskać jego kształt, potrzebujesz kolekcji permutacji wierszy / kolumn, co czyni matrycę nieco mniej odpowiednią. Trudniej jest też „zobaczyć” wykres, gdy jest już w tej formie.

Moje pytanie brzmi: czy istnieją jakieś „graficzne” algebry, które mogą opisać „kształt” wykresów?

Myślę o tym, jakie rodzaje formalnych systemów wymyślają algebraiczni topolodzy. W szczególności rzeczy takie jak algebra dla niezmienników węzłów lub systemy notacyjne, takie jak operady lub wariografy . Tego rodzaju „algebry bazgroły” nie są tak dobrze rozwinięte, więc być może istnieje powód, by sądzić, że taka algebra nie istnieje dla grafów, ale pomyślałbym, że zapytam, zanim założę inaczej.

AKTUALIZACJA:

Moje pytanie jest prawdopodobnie bardzo wąskie i nie można od razu odpowiedzieć „tak”, więc jeśli moderatorzy nie mają nic przeciwko, poszerzę je, pytając:

Czy istnieją jakieś istniejące systemy (takie, które opisuję powyżej), które można dostosować (łatwo lub w inny sposób) do stworzenia takiego systemu? Jeśli jest ich więcej, możesz wymienić je wszystkie. I wrzuć także te już wspomniane.

Motywacja

Moją motywacją do takiego pytania jest klasyfikacja wykresów asymetrycznych. Jestem tylko studentem, więc mój przegląd obecnego stanu teorii grafów algebraicznych jest dość cienki. Ale jeszcze nie widziałem wiele, jeśli w ogóle, pracy, która próbuje systematycznie opisywać wszystkie wykresy w sposób algebraiczny, w szczególności taki, który używa metafor wizualnych zamiast symbolicznych.

Praktyczny przykład, w którym taki system byłby użyteczny

Załóżmy, że ktoś chce opisać dowód, że wszystkie wykresy Eulera muszą mieć wierzchołki o równym stopniu. Standardowy dowód zwykle używa argumentów o stopniach parzystych i nieparzystych, nie wspominając o faktycznych zastosowanych krawędziach. Typowy uczeń po raz pierwszy znalazłby taki dowód i prawdopodobnie zaczął rysować wykresy, próbując przekonać się do argumentu. Być może jednak lepszym narzędziem niż czysty argument „logiczny” byłoby wykazanie, że jakikolwiek zbiór „symboli” z takiego języka nie spełniałby pewnego warunku „kompletności”.

Tak, wiem, w tej ostatniej części jestem falujący. Gdybym tego nie zrobił, prawdopodobnie sam bym zaczął tworzyć taki system!

Ale ignorując przez chwilę moją niejasność, mam wrażenie, że wiele starych i dobrze znanych twierdzeń z teorii grafów nie jest trudnych, ale wymaga pewnej konceptualizacji, że naprawdę dobry framework może „powiązać” i „spakować” w ujednolicony pogląd.

Wiele osób próbowało znaleźć język algebraiczny opisujący kształt wykresu. To pytanie zasadniczo motywuje teorię grafów strukturalnych .

Istotą tego obszaru matematyki dyskretnej jest badanie rozkładów grafów. Niektóre osoby pracujące w tym obszarze to Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković i ich współpracownicy, chociaż ta lista jest stronnicza z powodu moich własnych zainteresowań badawczych.

Poszczególne rodzaje rozkładów grafów doprowadziły do ​​jednych z najbardziej ogólnych wyników w teorii grafów. Na przykład jednym z głównych narzędzi technicznych opracowanych w ramach projektu dotyczącego nieletnich grafów, które doprowadziło do twierdzenia Robertsona-Seymoura , jest twierdzenie o strukturze grafu . To pokazuje, że klasy wykresów, które wykluczają niektóre drobne, można zbudować z prostszych wykresów.

W dowodzie twierdzenia Strong Perfect Graph zastosowano nieco inny rozkład. Kluczowy wynik to: Dla każdego wykresu Berge$G$, zarówno $G$ jest podstawowy lub jeden z $G, \overline{G}$ dopuszcza prawidłowe 2-złączenie, lub $G$ przyjmuje zrównoważoną partycję pochylenia.

Badane dotychczas dekompozycje są w pewnym sensie niealgebraiczne. Moją osobistą intuicją jest to, że istnieją oznaki, że nie ma „ładnego” systemu, takiego jak ten, którego szukasz. Uściślenie tego oświadczenia glib prawdopodobnie wymagałoby nietrywialnego przedsięwzięcia w teorii modeli skończonych, ale podejrzewam, że mogłoby to również prowadzić do interesujących nowych wyników w teorii grafów (czy to sukces, czy nie).

To pytanie jest ważne w programowaniu funkcjonalnym, ponieważ zwykła reprezentacja wykresów jest nieelegancka i nieefektywna w użyciu w językach wyłącznie funkcjonalnych.

Ładne podejście zostało zaprezentowane na ICFP w ubiegłym roku: „Wykresy algebraiczne z klasą (Perła funkcjonalna)” , autorstwa Andreya Mokhova.

Nie wiem, czy w pełni odpowiada twoim potrzebom, ale może reprezentować algebraicznie szeroką gamę różnych rodzajów grafów skierowanych i niekierowanych.