Қазақстан республикасының білім және ғылым министірлігі

Ішкі графтар және графтардың бөлігі

жүктеу 21,8 Mb. бет 93/214 Дата 09.01.2018 өлшемі 21,8 Mb. #7265 түрі Мазмұндама

Ішкі графтар және графтардың бөлігі. Граф бөліктерімен операциялар. Анықтама: Егер М1М және R1R∩(M1)2 болса, яғни G1 графының төбелер жиыны G графы төбелер жиынына, ал G1 қабырғалар жиыны G графының қабырғалар жиынына жатса G1- G бөлігі деп аталады. Анықтама Айталық. G=,G1=1,R1> графтары берілсін. Егер М1М және R1=R∩(M1)2 болса, яғни G1 графының төбелер жиыны G-ң төбелер жиынында жатса ал G1-ң доғалары екі жағымен де G графына жатса G1–G графының ішкі графы деп аталады. Анықтама.Егер Н графының төбелер жиыны V(H) мен қабырғалар жиыны E(H) G графының сәйкесінше төбелері мен қабырғалар V(G), E(G) жиындарында жатса және , онда Н графы G графының бөлігі деп аталады . Анықтама Егер , G графының бөлігі Н суграф деп аталады. Егер G графының кез келген төбесі Н графының ең болмаса бір қабырғасына инцидентті болса , онда бағытталмаған Н графы G графын жабады дейміз. Мысалы:а) G=<{1, 2, 3, 4}, {[1, 2], [1, 3], [1,4], [2,3], [3,4]}> б) G1=<{1, 2, 3}, {[1, 2], [1, 3], [2, 3]}>-G ішкі графы (М1МR1, R1=R∩R1) в) G11=<{1,2,3},{[1,2],(2,3)}>-G графының бөлігі (M11М,R11R∩(M11)2) жүктеу 21,8 Mb. Достарыңызбен бөлісу:

©g.engime.org 2024
әкімшілігінің қараңыз