Графтар: чокулар, кабыргалар, жолдор

Негизги түшүнүктөр

Граф — чокулар жана аларды туташтырган кабыргалар. Чокунун даражасы — андан чыккан кабыргалардын саны.

Кол алышуу леммасы: бардык чокулардын даражаларынын суммасы кабыргалардын санынын эки эселенгенине барабар. Ошондуктан так даражалуу чокулардын саны дайыма жуп.

$n$ чокулуу дарактын (циклсиз туташ графтын) так $n - 1$ кабыргасы бар.

Эң кыска жол

Кабыргалардын узундуктары оң болсо, Дейкстра алгоритми колдонулат: баштапкы чокуга $0$, калгандарына $\infty$ жазабыз; ар бир кадамда аралыгы эң кичине болгон бекитиле элек чокуну алып, анын коңшуларынын аралыктарын жаңыртабыз. Түз жол дайыма эле эң кыска боло бербейтин унутпаңыз!

Тордогу жолдордун саны

Багытталган циклсиз графта $A$дан ар бир чокуга чейинки жолдордун санын удаалаш эсептесе болот: чокуга келген жолдордун саны — ага кабырга менен кирген чокулардын маанилеринин суммасы.