Орындаған: Шады А
Бөліктік графтар, ішкі графтар, бӛліктік ішкі графтар
жүктеу/скачать 0.56 Mb.
|
| Бөліктік графтар, ішкі графтар, бӛліктік ішкі графтар
Егер H(X) графының барлық қабырғалары G(X) графының қабырғалары болса және H(X) графының тӛбелері G(X) графының тӛбелерімен сәйкес келсе, яғни x X ҥшін H(X) G(X) болса, онда H(X) графын G(X)- графы ҥшін бӛліктік граф деп аталады. Бөліктік граф қабырғалардың (доғалардың) бӛлігін қамтиды. Алғашқы берілген графқа байланысты бӛліктік граф бағдарланған немесе бағдарланбаған болуы мҥмкін. Кез келген граф ҥшін нӛл-графты оның бӛліктік графы деп санаймыз. G(X) графы ҥшін оның барлық бӛліктік H(X) графтарын H(X)-тің қабырғалары ретінде G(X)-тің әртҥрлі қабырғалар жиынын таңдап алу арқылы қҧруға болады. G(X) графының ішкі графы G (A) A деп тӛбелері A X жиынының элементтері болатын, ал қабырғалары екі ҧшы (басы мен соңы) A -да жататын G -ның қабырғалары болатын графты айтады. Яғни, ішкі граф тӛбелердің бір бөлігі мен осы тӛбелерді қосатын қабырғаларды қамтиды. Сонымен, G (A) A графы G(X)-тің ішкі графы, егер A X және GA (X) G(X) A болса. Егер A X болса, онда G (A) G(X) A . Бір ғана A {a} тӛбесі ҥшін G (a) A ішкі графы a -ның тҧзақтарынан қҧрылады. Егер A X жиыны G(X) графының оқшауланған тӛбелерінің ішкі жиыны болса, онда G(X) графының ішкі графы G (A) A нольдік граф болады. Негізгі графқа қатысты ішкі граф бағдарланған немесе бағдарланбаған болады. Екі ҧшы (басы мен соңы) A -да жататын G(X) графының кейбір қабырғаларынан тҧратын ішкі графты G(X) графының бӛліктік ішкі графы H (A),(A X) A деп атайды. Яғни, егер A X және кез келген x X ҥшін HA (X) G(X) A болса, онда H (A) A графы G(X) графының бӛліктік ішкі графы болады. G(X) графының толықтырушы бөліктік графы H(A) деп G(X) графының бӛліктік ішкі графы H (A) A -ға тиісті емес қабырғалардан тҧратын бір ғана графты айтады. жүктеу/скачать 0.56 Mb. Достарыңызбен бөлісу:
|