Сабақ тақырыбы: Графтардағы алгоритмдер
жүктеу/скачать 6,16 Kb.
|
Сабақтың мақсаты 10 5 практикалық есептерді шешу үшін графтарда-melimde.com
Буырсақ
- Бұл бет үшін навигация:
- Сабақтың мақсаты: 10.5.1.5 практикалық есептерді шешу үшін графтардағы алгоритмдерді іске асыру.
- Меңгерілетін білім
- Графтың түрлері
- Граф маршруты дегеніміз – көршілес төбелерді қосатын сол төбе лер мен қабырғалардың соңғы кезектелген тізбегі.
- Оқу тапсырмалары
|
Сабақтың мақсаты: 10 5 практикалық есептерді шешу үшін графтардағы алгоритмдерді іске асыру. Естеріңе түсіріңдер Сабақ тақырыбы: Графтардағы алгоритмдерСабақтың мақсаты: 10.5.1.5 практикалық есептерді шешу үшін графтардағы алгоритмдерді іске асыру.Естеріңе түсіріңдер:• сұрыптау деген не? • жылдам сұрыптау түрлері қандай? • көпіршікті сұрыптау деген не? Меңгерілетін білім:• «граф» түсінігі; • графтың түрлері; • графтағы іздеу алгоритмдері; • тереңнен іздеу; • көлденеңінен іздеу Графтар теориясы соңғы уақытта ғылым мен техниканың түрлі салаларында кеңінен қолданылады. Графтар теориясы алгоритмдеудің түрлі есептерін шешуге мүмкіндік беретін элект ронды есептеуіш машинаның пайда болуымен қарқынды дамыды. Граф – бұл екі жиынның жиынтығы: нүктелер жиыны мен сол нүк телердің кейбірін жұптап қосатын сызықтар жиыны. Нүктелер жи ыны графтың төбелері (түйіндері) деп аталады. Граф төбелерін қо сатын сызықтар жиыны графтың қабырғалары (доғалар) деп аталады. Графтың түрлеріБағытталған граф – барлық қабырғаларының бағыты бар граф, яғ ни қабырғаларына бағыт берілген. Бағытталмаған граф – барлық қабырғаларының бағыты жоқ граф, яғни қабырғаларына бағыт берілмеген. Аралас граф – бағытталған қабырғадан да, бағытталмаған қабырғадан да тұратын граф. Ілмек деп графтың өзіне өзін қосатын қабырғаны айтамыз. Егер екі төбені қосатын қабырға бар болса, онда ол төбелер көршілес деп аталады. Бірдей төбелер жұбын қосатын қабырғаларды еселі деп атайды. Қарапайым граф – ілмегі де, еселі қабырғалары да жоқ граф. Мультиграф – кез келген екі төбесі бір қабырғадан артық қабырға мен қосылған граф. Граф маршруты дегеніміз – көршілес төбелерді қосатын сол төбе лер мен қабырғалардың соңғы кезектелген тізбегі.Граф маршруты дегеніміз – көршілес төбелерді қосатын сол төбе лер мен қабырғалардың соңғы кезектелген тізбегі. Егер бастап қы және соңғы төбелер әр түрлі болатын болса, онда маршрут ашық деп аталады, ал кері жағдай да маршрут тұйық талған деп аталады. Егер маршрут төбелері әр түрлі болса, онда ол маршрут тізбек деп аталады. Егер ашық тізбекке кіретін төбелер әр түрлі болатын болса, онда ол тізбек жол деп аталады. Егер тұйықталған тізбекке кіретін төбелер (ақырғы төбе ден басқа) әр түрлі болса, онда ол тізбек цикл деп аталады. Егер графта деп кез келген екі төбе үшін оларды қосатын жол бар бол са, онда ол байланысқан граф деп аталады. Төбе салмағы – сол төбеге сәйкес (құн, өткізу қабілеті және т.б.) қойыл ған сан (нақты, бүтін немесе бөлшек). Қабырға салмағы (ұзындығы) – қабырғаға ұзындық, өткізу қабілеті және т.б. қатынаста берілетін сан немесе бірнеше сан. Өлшенген граф – әрбір қабырғаға қандай да бір мән (қабырға салмағы) қой ылған граф. Оқу тапсырмалары1. Граф деген не? 2. Графтың қандай түрлері бар? 3. Граф маршруты күнделікті өмірде қайда қолданылады? 4. Қабырғалар тізімі қалай құрылады? 5. Графтың көршілес тік матрица мен инцидиенттік матрица қалай құрылады? 6. Графтағы іздеу алгоритмдерінің қандай түрлері бар? 7. Тереңнен іздеу алгоритмі қалай орындалады? 8. Көлденеңінен іздеу алгоритмі қалай орындалады? http://melimde.com жүктеу/скачать 6,16 Kb. Достарыңызбен бөлісу:
|