Още определения – Уроци по програмиране

Дефиниция: Даден е ориентиран (неориентиран) граф G(V,E). Ако в множеството на ребрата му се допуска повторение (т.е. Е е мултимножество), G се нарича мултиграф.

Дефиниция: Даден е ориентиран граф G(V,E). Два върха i и j (i,j ∈ V) се наричат съседни, ако поне едно от ребрата (i,j) и (j,i) принадлежи на Е. В такъв случай още казваме, че i и j са краища за ребрата (i,j) и (j,i) . За всяко ребро (i,j) върхът i се нарича предшественик на j, а j – наследник на i. Всеки от върховете i и j се нарича инцидентен с реброто (i,j). Казваме, че две ребра са инцидентни, когато са инцидентни с един и същи връх. В случай на неориентиран граф, понятията съседен връх, край на ребро, инцидентност на върхове и ребра се дефинират аналогично.

Дефиниция: Път в ориентиран (неориентиран) граф G(V, E) се нарича последователност от върхове v1,v2,…vk такива, че за всяко i = 1,2,…k-1 е изпълнено (vi,vi-1) e от E. Върховете vi и vk се наричат краища на пътя. Ако v1 = vk, пътят се нарича цикъл. Ako за всяко i≠j(1≤i,j≤k)⇒vi≠vj, то пътят се нарича прост. Съответно, ако v1 = vk, и всички останали върхове са различни, цикълът се нарича прост. Когато граф съдържа поне един цикъл, той се нарича цикличен, а в противен случай – ацикличен.

Цикъл (контур)- път, за който началния и крайния възел съвпадат.

Прост цикъл – цикъл, в който няма повтарящи се възли.

Хамилтонов цикъл – цикъл, който включва всички възли на графа точно по веднъж.

Ойлеров цикъл – цикъл, който включва всички ребра на графа точно по веднъж.

Не всички графи притежават хамилтонов и ойлеров цикъл. Поради това, графите които притежават хамилтонов цикъл се наричат хамилтонови графи, а тези които притежават ойлеров цикъл- ойлерови графи