Бақылау сұрақтары:
Графтың цикломатикалық саны деген не?
Гамильтондық жол деген не?
Ағаштардың цикломатиялық саны неге тең?
Коммивояжер есебі дегеніміз не?
Цикломатикалық саны қалай анықталады?
Дәріс №9. Ағаштар. Ағаштардың қасиеттері
Графтағы циклдылық
Ағаштар
Графтағы циклдылық
Егер кезкелген G графтың қыры кем дегенде бір элементарлық циклге жататын болса, онда ол графтың қырын циклділік қыр деп атайды, ал қарсы жағдайда ациклділік деп атайды: Ациклділікке мысал ретінде ілінген қырды келтіруге болады. Төмендегі екі пікір орындалады:
1)Байланысты графтан циклдік қырды шығарғанда, оның байланыстылығы сақталады.
2) Ациклдік қырды шығарғанда байланыспайтын граф болып өзгереді.
Біріншіден кез келген тізбек үшін циклдік қырды циклдегі қалған қырлардың тізбегімен өзгертуге болады.
Екіншісі қарсы жолмен дәлелденеді, егер байланысты қалпында қалатын болса, онда алынған қырдың соңы элементарлық тізбекпен байланыста болар еді; алынған қырды орнына қойсақ, онда элементарлық цикл шығар еді, бұл мүмкін емес, себебі бұл қыр ациклді.
Достарыңызбен бөлісу: |
