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

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

Оддий графларнинг қуйидаги иккита ҳолини алоҳида айтиб ўтамиз:
- учли бўш граф -
- учли тўлиқ граф -
Қуйидаги шаклда ва графлар келтирилган
3-шакл.
2-таъриф. Учлари графнинг учларидан, қирралари эса тўпламдан иборат бўлган берилган графнинг тўлдирувчиси дейилади.
Р авшанки, . ва , бир-бирини тўлдирувчи графлардир. Уларга яна мисол келтирамиз

4-шакл.

3-таъриф. Aгар ва графлар учун , бўлса, у ҳолда граф нинг бўлаги дейилади.
Масалан,

5-шакл.

графлар 4-шаклдаги биринчи графнинг бўлакларидир.
4-таъриф. Агар графнинг бўлаги учун бўлса, у ҳолда у қисм граф дейилади.
Бошқача қилиб айтганда қисм графни ҳосил қилиш учун учлар тўплами билан уларнинг камида биттасига инцидент бўлган қирралар олиб ташланади.
Масалан, юқоридаги (4-шаклда) келтирилган графнинг қисмларидан баъзилари

6-шакл.
шулардан иборат.

5-таъриф. Агар графнинг бўлаги учун бўлса, у ҳолда у суграф дейилади, яъни суграфларни ҳосил қилиш учун фақат қирраларни олиб ташлаш кифоя.

Яна 4-шаклдаги мисолга мурожаат қиламиз. Қуйидаги

7-шакл.

графлар унинг суграфларидир.