Robbinsin lause , joka on nimetty amerikkalaisen matemaatikon Herbert Robbinsin mukaan [1] , sanoo, että graafit, joilla on vahvat suuntaukset , ovat täsmälleen 2-reunaan kytkettyjä graafeja . Eli jos ja vain jos voidaan valita suuntaamattoman graafin G jokaisen reunan suunta , jolloin graafista tulee suunnattu graafi , jossa on (suunnattu) polku mistä tahansa kärjestä mihin tahansa toiseen kärkeen, kun graafi G on yhdistetty eikä siinä ole siltoja .
Robbinsin kuvaajien luonnehdinta vahvoilla suuntauksilla voidaan todistaa käyttämällä korvahajottelua , Robbinsin tähän tarkoitukseen ehdottamaa työkalua.
Jos graafissa on silta, se ei voi olla korkeasti orientoitunut, koska valittiinpa suunta mikä tahansa, sillan kärjestä toiseen ei ole polkua.
Päinvastaisessa suunnassa on osoitettava, että mikä tahansa yhdistetty graafi ilman siltoja voi olla vahvasti orientoitu. Kuten Robbins osoitti, jokaisella sellaisella graafilla on osio aligraafien sekvenssiksi, jota kutsutaan "korviksi", ja tässä sekvenssissä ensimmäinen osagraafi on sykli, ja jokainen myöhempi osagraafi on polku, jonka lopulliset kärjet kuuluvat aiemmille "korville". järjestys. Jos suuntaamme kunkin "korvan" reunat siten, että saamme suunnatun syklin tai suunnatun polun, saamme koko graafin vahvan orientaation [2] .
Robbinsin teoreeman yleistys Boeschin ja Tyndellin [3] sekagrafeihin osoittaa, että jos graafissa G jotkut reunat ovat suunnattuja ja toiset eivät ole orientoituja, ja minkä tahansa pisteparin graafi G sisältää (suunnetun) polun, joka yhdistää nämä kärkipisteet ja ei riko olemassa olevia reunojen suuntia , niin mille tahansa graafin G suuntaamattomalle reunalle , joka ei ole silta , voidaan antaa suunta muuttamatta graafin G liitettävyyttä . Erityisesti suuntaamattomasta siltattomasta graafista voidaan tehdä vahvasti yhdistetty suunnattu graafi ahneella algoritmilla , joka määrittää askeleen reunan suunnan säilyttäen samalla polun olemassaolon minkä tahansa kahden kärkiparin välillä. Tällainen algoritmi ei voi juuttua tilanteeseen, jossa kaaren seuraavaa suuntaa ei voida valita.
Tietyn ohjaamattoman graafin voimakas orientaatio ilman siltoja voidaan löytää lineaarisessa ajassa suorittamalla graafista syvähaku , suuntaamalla polkua pitkin kaikki kärjet juuresta tulevaan suuntaan ja kaikki jäljellä olevat reunat jälkeläisestä esi-isään [4 ] Vaikka tämä algoritmi ei sovellu rinnakkaisiin laskentajärjestelmiin, koska syvyyshaku on monimutkainen toteuttaa näissä tietokoneissa, on olemassa vaihtoehtoisia algoritmeja, jotka ratkaisevat ongelman tehokkaasti rinnakkaislaskentamallissa [5] . Tunnetaan myös rinnakkaisalgoritmeja vahvasti kytkettyjen orientaatioiden löytämiseksi sekagraafille [6] .