Robbins teorem
Inom grafteorin säger Robbins sats , uppkallad efter Herbert Robbins ( 1939 ), att de grafer som har starka orienteringar är exakt de 2-kantsanslutna graferna . Det vill säga, det är möjligt att välja en riktning för varje kant av en oriktad graf G , förvandla den till en riktad graf som har en väg från varje vertex till varannan vertex, om och bara om G är ansluten och inte har någon bro .
Orienterbara grafer
Robbins karaktärisering av graferna med starka orienteringar kan bevisas med hjälp av öronnedbrytning , ett verktyg som introducerats av Robbins för denna uppgift.
Om en graf har en bro, kan den inte vara starkt orienterbar, för oavsett vilken orientering som väljs för bron kommer det inte att finnas någon väg från en av de två ändpunkterna på bron till den andra.
I den andra riktningen är det nödvändigt att visa att varje ansluten brolös graf kan vara starkt orienterad. Som Robbins bevisade, har varje sådan graf en uppdelning i en sekvens av subgrafer som kallas "öron", där den första subgrafen i sekvensen är en cykel och varje efterföljande subgraf är en bana, där de två vägändpunkterna båda tillhör tidigare öron i sekvensen. (De två banslutpunkterna kan vara lika, i vilket fall subgrafen är en cykel.) Orientering av kanterna inom varje öra så att det bildar en riktad cykel eller en riktad bana leder till en starkt sammankopplad orientering av den övergripande grafen.
Relaterade resultat
En utvidgning av Robbins teorem till blandade grafer av Boesch & Tindell (1980) visar att om G är en graf där vissa kanter kan vara riktade och andra oriktade, och G innehåller en väg som respekterar kantorienteringarna från varje vertex till varannan vertex, då kan vilken oriktad kant som helst av G som inte är en brygga göras riktad utan att ändra anslutningen av G . Speciellt kan en brolös oriktad graf göras till en starkt kopplad riktad graf med en girig algoritm som riktar kanter en i taget samtidigt som existensen av vägar mellan varje par av hörn bevaras; det är omöjligt för en sådan algoritm att fastna i en situation där inga ytterligare orienteringsbeslut kan fattas.
Algoritmer och komplexitet
En stark orientering av en given brolös oriktad graf kan hittas i linjär tid genom att utföra en djup-först-sökning av grafen, orientera alla kanter i djup-första sökträdet bort från trädroten, och orientera alla återstående kanter (som måste nödvändigtvis koppla en anfader och en ättling i djupet-första sökträdet) från ättling till anfader. Även om denna algoritm inte är lämplig för parallella datorer , på grund av svårigheten att utföra djupsökning på dem, finns alternativa algoritmer tillgängliga som löser problemet effektivt i parallellmodellen. Parallella algoritmer är också kända för att hitta starkt sammankopplade orienteringar av blandade grafer.
Ansökningar
Robbins motiverade ursprungligen sitt arbete med en ansökan om utformning av enkelriktade gator i städer. En annan tillämpning uppstår i strukturell styvhet , i teorin om gallerstöd . Denna teori handlar om problemet med att göra ett fyrkantigt galler, konstruerat av styva stavar fästa vid flexibla leder, stelt genom att lägga till fler stavar eller trådar som tvärstag på gallrets diagonaler. En uppsättning tillsatta stavar gör gallret stelt om en tillhörande oriktad graf är ansluten, och är dubbelt förstärkt (förblir stel om någon kant tas bort) om den dessutom är brolös. Analogt gör en uppsättning tillagda ledningar (som kan böjas för att minska avståndet mellan punkterna de ansluter, men inte kan expandera) rutnätet stelt om en tillhörande riktad graf är starkt ansluten. Omtolkning av Robbins sats för denna tillämpning är därför de dubbelt förstärkta strukturerna exakt de strukturer vars stavar kan ersättas av trådar samtidigt som de förblir stela.
Anteckningar
- Atallah, Mikhail J. (1984), "Parallell stark orientering av en oriktad graf" , Information Processing Letters , 18 (1): 37–39, doi : 10.1016/0020-0190(84)90072-3 , MR 0742079 .
- Baglivo, Jenny A. ; Graver, Jack E. (1983), "3.10 Bracing structures", Incidens and Symmetry in Design and Architecture , Cambridge Urban and Architectural Studies, Cambridge, Storbritannien: Cambridge University Press, s. 76–87, ISBN 9780521297844
- Balakrishnan, VK (1996), "4.6 Strong Orientation of Graphs", Introductory Discrete Mathematics , Mineola, NY: Dover Publications Inc., sid. 135, ISBN 978-0-486-69115-2 , MR 1402469 .
- Boesch, Frank; Tindell, Ralph (1980), "Robbins's theorem for mixed multigraphs", The American Mathematical Monthly , 87 (9): 716–719, doi : 10.2307/2321858 , JSTOR 2321858 , MR 8 0602822 .
- Clark, John; Holton, Derek Allan (1991), "7.4 Traffic Flow", A first look at graph theory , Teaneck, NJ: World Scientific Publishing Co. Inc., s. 254–260, ISBN 978-981-02-0489-1 , MR 1119781 .
- Gross, Jonathan L.; Yellen, Jay (2006), "Characterization of strongly orientable graphs", Graph Theory and its Applications , Discrete Mathematics and its Applications (2nd ed.), Boca Raton, FL: Chapman & Hall/CRC, s. 498–499, ISBN 978-1-58488-505-4 , MR 2181153 .
- Hopcroft, John ; Tarjan, Robert (1973), "Algorithm 447: efficient algorithms for graph manipulation", Communications of the ACM , 16 (6): 372–378, doi : 10.1145/362248.362272 , S2CID 14772567 .
- Robbins, HE (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , JSTOR 2303897 .
- Roberts, Fred S. (1978), "Kapitel 2. The One-Way Street Problem", Graph Theory and its Applications to Problems of Society , CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 29, Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM), s. 7–14, ISBN 9780898710267 , MR 0508050 .
- Soroker, Danny (1988), "Snabb parallell stark orientering av blandade grafer och relaterade förstärkningsproblem", Journal of Algorithms , 9 (2): 205–223, doi : 10.1016/0196-6774(88)90038-7 , MR 6093610 .
- Vishkin, Uzi (1985), "Om effektiv parallell stark orientering", Information Processing Letters , 20 (5): 235–240, doi : 10.1016/0020-0190(85)90025-0 , MR 0801988 .