Графтар саны. Ағаштар

1 Цикломатикалық сан
2 Хроматикалық сан
3 Ағаштар, ағаштардың негізгі қасиеттері
4 Граф қаңқасы
5 Графтардағы маршруттар

Цикломатикалық сан. Бағытталмаған G(V, E) графы берілсін. υ(G)=m-n+p, Мұндағы m–граф қабырғаларының саны; n–граф төбелерінің саны; p–байланысты компоненттер саны G(V, E) графының цикломатикалық саны деп аталады. Цикломатикалық санының физикалық мағынасы бар: ол графтың тәуелсіз циклдарының санына тең. Электр шынжырларын есептеген кезде цикломатикалық сан тәуелсіз контурлар санын есептеуге қолданылады.
1-Теорема.Егер G1 графы G графының суграфы болса, онда υ(G1)≤ υ(G).
2-Теорема.Байланысты графта цикл болмауы үшін υ(G)=0 қажетті және жеткілікті.
3-Теорема. Егер G графтың екі байланысты G1 және G2 компоненттері бар болса, онда υ(G)=υ(G1)+υ(G2).
4-Теорема. Графта цикл болмауы үшін υ(G)=0 қажетті және жеткілікті.
Айталық, G(V, E) бағытталмаған граф. G графының S1, S2,…,Sk циклдар жүйесі сызықты тәуелді деп аталады, егер қандай да бір i1, i2, …,ir (1≤ i1 ≤ i2 ≤…≤ ir ≤ k) Si1∆ Si2∆…∆Sik ноль граф болса. Керісінше болса S1, S2, …,Sk циклдары сызықты тәуелсіз циклдар деп аталады. Сызықты-тәуелсіз циклдардың ең көп саны G графындағы тәуелсіз циклдар саны деп аталады.
5-Теорема. Графтың цикломатикалық саны оның тәуелсіз циклдарының санына тең.
Хроматикалық сан. Әр төбесіне қандай да бір бояу сәйкестендірілген және сыбайлас төбелер әртүрлі бояулармен боялған граф деп аталады. G графын дұрыс бояуға қажетті бояулардың саны оның хроматикалық саны деп аталады және χ(G) болып белгіленеді.
6-Теорема.G графы ноль-граф болса ғана бір хроматикалы граф болады.
7-Теорема (Кениг теоремасы). Граф бихроматикалы болуы үшін онда тақ ұзындықты қарапайым цикл болмауы қажетті және жеткілікті.
Ағаштар, ағаштардың негізгі қасиеттері. Шексіз бағытталмаған байланысты граф ағаш деп, ал циклсыз байланыссыз граф орман деп аталады. Анықтама бола алатындай G ағашының кейбір қасиеттерін қарастырамыз:
а) G байланысты және циклы жоқ;
б) G циклы жоқ және n-1 қабырғасы бар;
в) G байланысты және n-1 қабырғасы бар;
г) G графында цикл жоқ, бірақ сыбайлас емес төбелер арасында қабырға қосу тек бір ғана циклдың пайда болуына әкеледі;
д) G байланысты, бірақ бұл қасиетін кез келген қабырға алынып тасталса жоғалтады;
е) G графының кез келген төбелер жұбы тек бір ғана шынжырмен байланысқан.
Граф қаңқасы.
8-Теорема. Граф байланысты болса ғана орман болатын суграф болады.
Орман болатын G суграфы қаңқалы ағаш немесе G суграфының қаңқасы деп аталады.