Главная страница
Навигация по странице:

  • Графттарда минимал жане максимал бутақ ағаштары

  • Алгоритм № 7.

  • 6 7 8 Гоха. Графтарда ашытытар. Граф диаметрі радиусы жне орталыы


    Скачать 40.34 Kb.
    НазваниеГрафтарда ашытытар. Граф диаметрі радиусы жне орталыы
    Дата12.09.2022
    Размер40.34 Kb.
    Формат файлаdocx
    Имя файла6 7 8 Гоха.docx
    ТипДокументы
    #673929

    Графтарда қашықтықтар. Граф диаметрі радиусы және орталығы
    Айталық G = (V,X) – граф (жалпы жағдайда псевдограф) берілген болсын. Егер υ,ω V, υ ≠ ω төбелер болса, онда екі төбені жалғастыратын маршрут бар және олардың ішінен минимал маршрут табу мүмкіндігін байқаймыз. Шынында, егер к1 ұзындықтағы q1 маршрут минимал болмаса, онда к2 < к1 ұзындықтағы q2 маршрут табылады. Егер q2 маршрут минимал болмаса, онда к3 < к2 ұзындықтағы q3 маршрут бар болады және т.б.

    Осы секілді маршруттардың ұзындығын кемітуді (к1–1) ретке дейін ғана мүмкіндігін көру қиын емес, себебі өте минимал маршруттың ұзындығы бірге тең. Соның үшін G да υ,ω төбелерді қосатын минимал маршрут міндетті түрде табылады.

    Осы маршруттың ұзындығын d(υ,ω) арқылы белгілейміз. Сонымен кез келген υ V төбе үшін d(υ,υ)=0.Тағыда кез келген υ,ωV үшін G да υ,ω (υ≠ω)төбелерді қосатын маршрут болмаса, онда d(υ,ω) = +∞ немесе d(υ,ω) = ∞ ретінде жазамыз. Сонымен кез келген υ,ω V төбелер үшін d(υ,ω) шаманы анықтадық.

    Осы d(υ,ω) – шаманы υ , ω төбелер арасындағы қашықтық деп айтамыз.

    d(υ,ω) қашықтық метрикалық аксиомаларды қанағаттандырады:

    1.d(υ,ω) ≥ 0, бұл жерде d(υ,ω) = 0 теңдік υ = ω болғанда және тек сонда ғана орынды ;

    1. d(υ,ω) = d(ω,υ);

    2. d(υ,ω) ≤ d(υ,u) + d(u,ω), бұл жерде υ,u,ω – G графтың кез келген төбесі ;

    3. d(υ,ω) < ∞.


    Граф диаметрі, радиусы және орталығы.
    Айталық G = (V,X) – байлаынсты граф немесе жалпы жағдайда псевдограф болсын.

    1. Онда d(G) = max d(υ,ω)

    υ,ω V

    шекті шама болады және G графтың диаметрі деп айтылады.

    2. Егер υ  V кез келген төбе болса, онда

    r(υ) = max d(υ,ω)

    ω V

    шекті шама G графтағы υ төбенің максимал эксцентриситетті (алыстағы) нүктесі деп айтылады.

    3. G графтың радиусы деп

    r(G) = min r(υ)

    υ V

    шаманы айтамыз.

    4. Кезкелген υ V үшін r(υ) = r(G) болған төбе G графтың орталығы деп айтылады.

    19 – мысал. 16 – сызбада бейнеленген G граф үшін : d(G) = 3, r(υ1) = 3, r(υ2) = 2, r(υ3) = 2, r(υ4) = 2, r(υ5) = 3, r(G) = 2 ; υ2, υ3, υ4 – G графтың орталықтары.

    υ3

    υ5

    υ1 υ2

    υ4
    16-сызба.
    Графттарда минимал жане максимал бутақ ағаштары
    Тиелген графтардың минимал бұтақ ағаштары.
    Айталық байланысты G = (V,X) графтың әр бір xÎ X қабырғасына ℓ(x) – қабырқа ұзындығы сәйкес қойылған, яғни G тиелген граф болсын.

    Анықтама. Байланысты тиелген G граф бұтақ ағашының өзінде болған қабырғалар ұзындықтары қосындысы минимал болған ағаш G графтың минимал бұтақ ағашы (МБА) деп айтылады.

    Енді G граф үшін МБА табу алгоритімін келтіреміз.

    Алгоритм № 7. (Байланысты тиелген G графтан МБА ны бөлү):

    1 – қадам. G графта минимал ұзындықтағы қабырға айырып аламыз. Ол өзіне инцидентті болған төбемен G2 ішграфты құрайды. i = 2 болсын.

    2 – қадам. Егер i = n болса (n = n(G)), онда G1 – ізделінген МБА деп қабылданып, мәселе соңына жетеді. Басқа жағдайда 3 – қадамға өтеміз.

    3 – қадам. Енді Gi де жатпайтын, Gi графтағы қалайда бір төбеге инцидентті болған және G графтың барлық қабырғалары ішінен таңдалған минимал ұзындықтағы жаңа қабырғаны Gi графқа қосып Gi+1 граф құраймыз. Осы қабырғамен бірге оған инцидентті болған, бірақ Gi де жатпайтын төбеніде Gi+1 ге енгіземіз. i:=i+1 орындап 2 – қадамға өтеміз.

    29 – мысал. 27 – сызбада бейнеленген G тиелген графтың МБА сын алгоритм негізінде анықтаймыз. 28 - сызбада алгоритмді орындау нәтижесінде алынған Gi, i = 2, 3,4,5 графтар тізбегі келтірілген. Бұл жерде n(G)=5 болғандықтан G графтың МБАсы G5 болады.

    υ2 2 υ3

    1 u5 4

    1 3

    5 3

    υ1 4 υ4


    написать администратору сайта