Transponera graf
I den matematiska och algoritmiska studien av grafteori är motsatsen , transponeringen eller omvändningen av en riktad graf G en annan riktad graf på samma uppsättning hörn med alla kanter omvända jämfört med orienteringen av motsvarande kanter i G. Det vill säga, om G innehåller en kant ( u , v ) så innehåller den omvända/transponera/omvända av G en kant ( v , u ) och vice versa.
Notation
Namnet converse uppstår eftersom omkastningen av pilar motsvarar att ta motsatsen till en implikation i logik. Namnet transponera beror på att den närliggande matrisen för den transponerade riktade grafen är transponeringen av den närliggande matrisen för den ursprungliga riktade grafen.
Det finns ingen allmän överenskommelse om föredragen terminologi.
Det omvända betecknas symboliskt som G' , G T , G R , eller andra notationer, beroende på vilken terminologi som används och vilken bok eller artikel som är källan till notationen.
Ansökningar
Även om det är liten matematisk skillnad mellan en graf och dess transponering, kan skillnaden vara större inom datavetenskap, beroende på hur en given graf representeras . Till exempel, för webbgrafen , är det lätt att bestämma de utgående länkarna för en vertex, men svårt att bestämma de inkommande länkarna, medan i omkastningen av denna graf är det motsatta sant. I grafalgoritmer kan det därför ibland vara användbart att konstruera en explicit representation av omkastningen av en graf, för att sätta grafen i en form som är mer lämplig för de operationer som utförs på den. Ett exempel på detta är Kosarajus algoritm för starkt anslutna komponenter , som tillämpar djup-först-sökning två gånger, en gång på den givna grafen och en andra gång på dess omkastning.
Relaterade begrepp
En skevsymmetrisk graf är en graf som är isomorf till sin egen transponeringsgraf, via en speciell typ av isomorfism som parar ihop alla hörn.
Den omvända relationen för en binär relation är den relation som omvänder ordningen för varje par av relaterade objekt. Om relationen tolkas som en riktad graf är detta samma sak som transponeringen av grafen. I synnerhet kan den dubbla ordningen av en partiell ordning tolkas på detta sätt som transponeringen av en transitivt stängd riktad acyklisk graf .
Se även
- Omvänd relation – Omvänd ordning av element i en binär relation