Мавзу: граф алгоритмлари 1-§. Оддий графлар. Таъриф ва мисоллар Калит сўзлар

2-§. Графларнинг изоморфлиги


Графлар изоморфизми. Изоморф графлар. Қўшнилик муносабати.


ва графлар берилган бўлсин. Қайси ҳолда улар иккаласи битта графни ифодалайди деган саволга жавоб беришга уринамиз.
Бу масала графларнинг изоморфизми тушунчаси билан чамбарчас боғликдир.
Таъриф. Агар ва графларнинг учлари тўпламлари ва орасида ўзаро бир қийматли ва учларнинг қўшнилик муносабатини сақлайдиган мосликни ўрнатиш мумкин бўлса, яъни ва уларга мос бўлган учун бўлса, у ҳолда бу графлар изоморф дейилади.

Қуйидаги графлар берилган бўлсин

, , бу ерда
, ;
, ;
, ;
, .




G₁ G₂ G₃ G₄

8-шакл.
Умуман олганда бу графларнинг тўрталаси ҳар хилдир. , чунки ; , чунки . Лекин кўриниб турибдики, ва бир хил тузилишга (структурага) эга, шу жумладан, ва ҳам бир хил тузилишга эга. Агар изоморфликни  ва изоморф эмасликни  белгиласак: , , G₁ G_3, G₁G4, G₂ G₃, G₂ G₄ эканлигини кўрамиз.

Масалан, ни қуйидагича аниқлаш мумкин
, , , ;
у ҳолда
ва , ва ,
ва , ва ,
ва , ва ,
яъни шарт бажарилади.
Ўқувчига

мослик ҳам ва графларнинг изоморфизми эканлигини текширишни тавсия қиламиз. Шу билан бирга учларнинг қолган 4!- 2=22 мосликларни изоморфизм эмаслигини айтиб ўтамиз.
ва графларнинг изоморфизмини масалан, қуйидагича ўрнатиш мумкин
1 2 3 4 - графда

1 3 2 4 - графда
(бу графларнинг бошқа изоморфизмларини аниқланг).
эканлигини осонгина аниқлаш мумкин: Масалан, графнинг 4 учи фақат битта уч билан қўшни, да эса бундай уч умуман йўқ.