Gångbarhet för diagram

Det finns många problem i grafteorin som handlar om korsande grafer . Man gör en åtskillnad mellan problem när man passerar kanterna och problem när man passerar noderna . De viktigaste problemen av denna typ presenteras kort nedan.

Euler cirkel problem

Euler-cirkelproblemet undersöker framgången för kanterna i en graf. Frågan här är om det finns en cykel som går genom alla kanter av grafen exakt en gång. Det bör noteras att det är nödvändigt och tillräckligt om grafen angränsar och alla noder har raka grader . Den här egenskapen kan enkelt kontrolleras linjärt med hjälp av djup-först-sökning . Det är också möjligt att hitta en sådan cykel (om den finns) med en linjär körtid.

Brevbärarproblem

Det kinesiska brevbärarproblemet ber om en kortaste rutt över alla kanter i en kantvägd graf . För grafer som har en Euler-cirkel motsvarar denna rutt uppenbarligen en Euler-cirkel. I andra grafer måste kanterna nödvändigtvis passeras flera gånger. Längden på dessa kanter måste minimeras. För detta ändamål är det tillräckligt att hitta en minsta perfekt parning i avståndsdiagrammet för alla noder med en udda grad. Detta är möjligt på polynomtid. Enligt kanterna på denna parning måste tillhörande kanter dupliceras i originaldiagrammet. Detta skapar en graf som har en Euler-cirkel. Det räcker nu att hitta en Euler-cirkel.

Hamilton cykelproblem

Hamilton-cykelproblemet undersöker framkomligheten för noderna i en graf. Frågan är om det finns en cirkel som innehåller varje nod i grafen. Problemet är NP-komplett . Några tillräckliga och nödvändiga förhållanden för förekomsten av en Hamilton-cykel är kända, så att det är möjligt att effektivt kontrollera några diagram om de har en Hamilton-cykel.

Säljare Problem

Den resande säljare problem ber om en kortaste rundresa över alla noder i en kant vägda komplett graf. Detta problem är också NP-komplett. Med hjälp av några rimliga antaganden ( ojämlikhet i triangeln ) är det möjligt att behandla problemet åtminstone ungefär .