Бағытталмаған граф қабырғалар тізімімен берілген: A–B, A–C, B–D, C–D, C–E, D–F, E–F. A төбесінен F төбесіне дейін қабырғалар саны бойынша неше түрлі ең қысқа жол бар?
Жауап пен талдауды көрсетуЖауап пен талдауды жасыру
Дұрыс жауап
- A3
Талдау
A төбесінен енге қарай іздеу арқылы қашықтықтарды табамыз: A — 0; B және C — 1; D және E — 2; F — 3. Төбеге баратын ең қысқа жолдар саны алдыңғы деңгейдегі көрші төбелердің жолдар санының қосындысына тең: B-ға бір жол, C-ға бір жол, D-ға екі жол (B және C арқылы), E-ге бір жол (C арқылы). F-ке D және E келеді, сондықтан 2 + 1 = 3 жол: A–B–D–F, A–C–D–F, A–C–E–F. «4» мәні ұзынырақ A–B–D–C–E–F жолын қоса, барлық қарапайым жолдарды санағанда шығады. «2» мәні тек D арқылы өтетін жолдарды ғана ескергенде шығады.