Wykres transpozycji
W matematycznym i algorytmicznym badaniu teorii grafów odwrotność , transpozycja lub odwrotność grafu skierowanego G jest kolejnym grafem skierowanym na tym samym zestawie wierzchołków ze wszystkimi krawędziami odwróconymi w porównaniu z orientacją odpowiednich krawędzi w G. To znaczy, jeśli G zawiera krawędź ( u , v ) , to odwrotność/transpozycja/odwrotność G zawiera krawędź ( v , u ) i odwrotnie.
Notacja
Nazwa converse powstaje, ponieważ odwrócenie strzałek odpowiada przyjęciu odwrotności implikacji w logice. Nazwa transpozycja wynika z tego, że macierz sąsiedztwa grafu skierowanego transpozycją jest transpozycją macierzy sąsiedztwa oryginalnego grafu skierowanego.
Nie ma ogólnej zgody co do preferowanej terminologii.
Odwrotność jest oznaczona symbolicznie jako G' , GT zależności od tego , GR lub inne zapisy, w , jaka terminologia jest używana i która książka lub artykuł jest źródłem zapisu.
Aplikacje
Chociaż matematycznie istnieje niewielka różnica między wykresem a jego transpozycją, różnica może być większa w informatyce , w zależności od tego, jak dany wykres jest reprezentowany . Na przykład w przypadku wykresu sieciowego łatwo jest określić wychodzące łącza wierzchołka, ale trudno określić łącza przychodzące, podczas gdy w odwróceniu tego grafu jest odwrotnie. W algorytmach grafowych , dlatego czasami może być przydatne skonstruowanie jawnej reprezentacji odwrócenia grafu, aby nadać grafowi postać bardziej odpowiednią do wykonywanych na nim operacji. Przykładem tego jest algorytm Kosaraju dla silnie połączonych komponentów , który dwukrotnie stosuje przeszukiwanie w głąb , raz do danego grafu i drugi raz do jego odwrócenia.
Pojęcia pokrewne
Graf skośno-symetryczny to graf, który jest izomorficzny z własnym grafem transpozycji, dzięki specjalnemu rodzajowi izomorfizmu, który łączy w pary wszystkie wierzchołki.
Relacja odwrotna relacji binarnej to relacja, która odwraca kolejność każdej pary powiązanych obiektów. Jeśli relacja jest interpretowana jako graf skierowany, jest to to samo, co transpozycja grafu. W szczególności podwójny porządek rzędu częściowego można interpretować w ten sposób jako transpozycję przechodnie zamkniętego skierowanego wykresu acyklicznego .
Zobacz też
- Relacja odwrotna – Odwrócenie kolejności elementów relacji binarnej