En bana i en graf är en sekvens av hörn där varje hörn är ansluten till nästa kant.
Låt G vara en oriktad graf . En bana i G är en ändlig eller oändlig sekvens av kanter och hörn [1] ,
att varannan angränsande kanter och har en gemensam vertex .
Således kan man skriva
Observera att samma kant kan förekomma flera gånger i en bana. Om det inte finns några kanter som föregår , då kallas det den initiala spetsen av S, och om det inte finns några kanter efter , då kallas den för den sista spetsen av S. Varje vertex som tillhör två intilliggande kanter kallas intern . Eftersom kanter och hörn kan upprepas i en bana, kan en inre vertex vara start- eller slutpunkten.
Om start- och slutpunkten är desamma kallas banan cyklisk . En bana kallas en kedja , och en cyklisk bana kallas en cykel , om var och en av dess kanter inträffar högst en gång (hörn kan upprepas). En icke- cyklisk bana kallas en enkel bana om ingen vertex upprepas i den. En cykel med ett slut kallas en enkel cykel om det inte är ett mellanliggande hörn i den och inga andra hörn upprepas.
Tyvärr är denna terminologi inte väl etablerad. Wilson [2] skrev:
Det vi har kallat en rutt kallas också för en stig, en kantsekvens.
Kedjan kallas en väg, en halvenkel väg; en enkel kedja - en kedja, en bana, en båge, en enkel bana, en elementär kedja; en sluten krets - en cyklisk krets, en krets; cykel - en kontur, en konturkrets, en enkel cykel, en elementär cykel.
— [3] [4] [5]Banor, kedjor och cykler är grundläggande begrepp inom grafteori och definieras i den inledande delen av de flesta grafteoriböcker. Se till exempel Bondi och Marty [6] , Gibbons [7] eller Distel [8] .
En bana för vilken inga grafkanter förbinder två hörn av banan kallas en inducerad bana .
En enkel bana som innehåller alla hörn i en graf utan upprepningar är känd som en Hamiltonsk bana .
En enkel cykel som innehåller alla hörn i en graf utan upprepningar är känd som en Hamiltonsk cykel .
Cykeln som erhålls genom att lägga till en kant av grafen till det spännande trädet i den ursprungliga grafen är känd som Fundamental Cycle.
Två banor är vertexoberoende om de inte delar inre hörn. På samma sätt är två banor kantoberoende om de inte delar inre kanter.
Banlängden är antalet kanter som används i banan, med återanvändbara kanter som räknas motsvarande antal gånger. Längden kan vara noll om banan består av endast en vertex.
En viktad graf associerar varje kant med något värde ( kantvikt ). Vikten av en bana i en viktad graf är summan av vikterna av banans kanter. Ibland används istället för ordet vikt pris eller längd .