Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар

жүктеу 0,75 Mb.

бет	8/23
Дата	03.02.2022
өлшемі	0,75 Mb.
	#35463

1 ... 4 5 6 7 8 9 10 11 ... 23

лекция

Цикломатикалық сан. Бағытталмаған G(V, E) графы берілсін. υ(G)=m-n+p, Мұндағы m–граф қабырғаларының саны; n–граф төбелерінің саны; p–байланысты компоненттер саны G(V, E) графының цикломатикалық саны деп аталады. Цикломатикалық санының физикалық мағынасы бар: ол графтың тәуелсіз циклдарының санына тең. Электр шынжырларын есептеген кезде цикломатикалық сан тәуелсіз контурлар санын есептеуге қолданылады.

1-Теорема.Егер G1 графы G графының суграфы болса, ондаυ(G1)≤ υ(G).

2-Теорема.Байланысты графтацикл болмауы үшін υ(G)=0 қажетті және жеткілікті.

3-Теорема.Егер G графтың екі байланыстыG₁және G₂ компоненттері бар болса, онда υ(G)=υ(G₁)+υ(G₂).

4-Теорема.Графта цикл болмауы үшін υ(G)=0 қажетті және жеткілікті.

Айталық, G(V, E) бағытталмаған граф. G графының S₁, S₂,…,S_k циклдар жүйесі сызықты тәуелді деп аталады, егер қандай да бір i₁, i₂, …,i_r (1≤ i₁ ≤ i₂≤…≤ i_r ≤ k) S_i1∆ S_i2∆…∆S_ikноль граф болса. Керісінше болса S₁, S₂, …,S_k циклдары сызықты тәуелсіз циклдар деп аталады. Сызықты-тәуелсіз циклдардың ең көп саны G графындағы тәуелсіз циклдар саны деп аталады.

5-Теорема. Графтың цикломатикалық саны оның тәуелсіз циклдарының санына тең.

жүктеу 0,75 Mb.

Достарыңызбен бөлісу:

1 ... 4 5 6 7 8 9 10 11 ... 23