https://en.wikipedia.org/wiki/Cayley_graph#/media/File:Cayley_graph_of_F2.svg
Subscribe to:
Post Comments (Atom)
Spin Chronicles Part 28: Left and Right Regular
As it is Sunday, and Christmas Eve is coming soon - it should be an easy talk today. In fact it is my intention that everything should be ...
-
This is the beginning of a new series of posts by Laura Knight-Jadczyk (if you are curious - my wife). I was curious about Goff's views... -
The world around us is not merely changing; it is experiencing a quantum leap. This is not a mere evolution but a dramatic transformation,... -
Reading A. Yu. Savin , "From the depths of the subconscious. Poems, thoughts, stories " . And there these thoughts: "- Do...
To zdaje się stosunkowo klarowne, przynajmniej na początku: https://www.mimuw.edu.pl/~amn/Rados%C5%82awJ%C4%99drych.pdf
ReplyDeleteAch, ale tu jest ciekawsza kwestia!!! Przecież izomorfizm pomiędzy grafami będzie stanowić relację równoważności!!!!!!!
ReplyDeleteTak mi się w tej chwili zdaje. Możemy to sprawdzić, bowiem całkiem mi się podoba ta teoria grafów. I teraz już ja widzę pewne ciekawe zastosowanie. Niemniej jednak nie wiem nawet czy to czytasz, więc poczekam, aż się dowiem. Pytanie czy jest Ci to w ogóle potrzebne. Jak Ty to widzisz?
Przez pomyłkę usunąłem ten komentarz Liwiusza:
ReplyDeleteTo też jest dość przystępne moim zdaniem: https://matematyka.pl/viewtopic.php?t=430352
W tej pierwszej pracy on dalej pisze o pętlach etc. I są faktycznie klasy abstrakcji, ale można to prościej zrobić i mogę to zrobić za chwilę. Może to Ci w czymś pomoże. I zdaje się, że tak być musi. Izomorfizm będzie relacją równoważności. Ale jeżeli już to wiesz to nie będę wyjaśniać dlaczego ja tak uważam. A jeżeli nie wiesz to Ci napiszę.
ReplyDeleteJak to widzę:
ReplyDeleteZ książki z linku:
Grafem nazywamy parę (V,E), gdzie V jest zbiorem punktów zwanych wierzchołkami, a E \subseteq V^2 jest zbiorem par wierzchołków nazywanych krawędziami.
Potem w tej książce jest graf Cayleya, w definicji 1.2.2.
Ale z tego, co mnie interesuje na tę chwilę:
Weźmy 2 grafy. G=(V(G),E(G)) i H=(V(H),E(H)).
Jeżeli istnieje bijekcja F:V(G) -> V(H) taka, że dla każda krawędź \in E(G) to przecież F od krawędzi musi należeć do E(H).
Kontynuacja w toku.
Stąd od razu widać, że zarówno F, jak i F^-1 czyli z V(H) na V(G) będą homomorfizmami, a zatem grafy G i H są izomorficzne.
ReplyDeleteTo teraz weźmy jakieś nowe grafy, niech się zwą X, Y, Z.
X=(V(X),E(X)) i tamte analogicznie, jedynie Y lub Z zamiast X.
Czy są zwrotne? Tak, bowiem przecież wierzchołki będą odwzorowywane na siebie.
Czy są symetryczne? Tak, bowiem jak teraz ta nasza F odwzoruje te wierzchołki to F^-1 odwzoruje na odwrót. Ale jeżeli jest taka potrzeba to mogę to zapisać wszystko po kolei.
Ale będzie symetryczna. To widać.
A czy przechodnia?
Tu chyba należałoby wprowadzić dwa odwzorowania i złożyć je ze sobą celem dowiedzenia tej własności, więc to muszę przemyśleć czy w ten sposób…
Zmienię oznaczenia, ponieważ w tamtych literki by się poplątały. Ale to tylko nazwy. Więc nazwijmy te grafy G1, G2, G3.
ReplyDeleteWcześniej mieliśmy tylko izomorfizm F, teraz musimy mieć 2. F1 i F2.
F1 będzie z V(G1) na V(G2).
F2 oczywiście z V(G2) na V(G3).
Jednak F3 stanowiące złożenie F1 i F2 będzie przecież bijekcją z V(G1) na V(G3). Dlaczego?
Teraz mamy te wierzchołki, a1, b2 \in V(G1) itd.
I oczywiście F1(a1) = a2 i F1(b1) = b2 i analogicznie dla F2 oraz a2, b2, a3, b3.
I przecież same te a i b będą sąsiadujące jedynie wówczas, kiedy F(…) też będą. To samo dotyczy F3, czyli złożenia. A zatem F3 jest izomorfizmem. Czyli przechodniość będzie zachowana.
A więc jest relacją równoważności faktycznie. I teraz możemy przejść do grafu Cayleya.
W tej definicji 1.2.2. e jest krawędzią, czyli parą (a,b) wierzchołków z Twojego rysynku.
ReplyDeleteTo jest zrozumiałe. Jednak z czym konkretnie masz problem? Co chcesz zrozumieć?
"Jak powstał ten rysunek?".
ReplyDeleteZabierzmy wszystkie te fraktale i wyobraź sobie, że masz na razie na tym rysunku sam krzyż. b1 i b2 niech będą pionowe i a1, a2 niech będą poziome. A ponadto masz F - bijekcję, która zachowuje krawędzie, czyli automorfizm grafów. Jeżeli masz krzyż i nie masz kierunków to masz 4! automorfizmów. Widzisz to?
Ale 4! masz tylko wtedy, kiedy nie masz kolorów i kierunków, a w grafie Cayleya je masz. Jak się w ten sposób ograniczysz, to w tym krzyżu możesz mieć tylko 2*2 automorfizmy w sensie grafu Caylea, ze względu na kolor i kierunek.
ReplyDeleteW tym filmie on nie rysuje dokładnie tego, ale mówi o metodzie: https://www.youtube.com/watch?v=PfRqs9W8nPQ
ReplyDeleteTo też się jawi bardzo ciekawie, bardzo: http://weddslist.com/groups/cayley.html
ReplyDeleteTo również może Cię zainteresować: https://www.researchgate.net/publication/255484754_Generalized_Linear_Cellular_Automata_in_Groups_and_Difference_Galois_Theory
ReplyDeleteI to: https://www.math.columbia.edu/~alessandrini/Courses/Undergraduate_Seminars-s2020/Cayley%20Graphs%20of%20Free%20Groups_GSanchez.pdf
ReplyDeleteStrona 17.
I jeszcze to: https://www.researchgate.net/publication/2723168_Growth_Functions_and_Automatic_Groups
ReplyDeleteA tu jest chyba jeszcze prościej: http://pi.math.cornell.edu/~mec/2008-2009/Victor/part4.htm
ReplyDelete