Анықтама: G1, G2 графтарының бірігуі деп G1UG2=1UM2,R1UR2> графын айтады.
Анықтама:ЕгерМ2∩М2= онда G1,G2 графының қиылысуы деп, G1∩G2=1∩M2,R1∩R2> графын айтады.
Анықтама: G1, G2 графтарының сақиналы қосындысы деп G1 G2=1UM2,R1 R2>, мұндағы R1 R2=( R1\R2)U(R2 \R1).
1
№9 дәріс
Қарастырылатын сұрақтар (дәріс жоспары):
1. Цикл.
2. Эйлер және Гамильтон циклдары.
3. Цикломатикалық және хроматикалық сан.
Дәрістің қысқаша мазмұны:
Цикломатикалық сан.Бағытталмаған 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-Теорема. Графтың цикломатикалық саны оның тәуелсіз циклдарының санына тең.
