Графлар устида амаллар

TT-21-03
UBAYDULLAYEV SHOHJALIL

FAN:DISKRET TUZULMALAR

5-mustaqil ish

ГРАФЛАР УСТИДА АМАЛЛАР

2.1 Графлар назарияси фани – чизиқлар ва нуқталардан тузилган баьзи бир геометрик конфигурациялар тўғрисидаги масалаларни ечишда ишлатилади. Бундай масалаларни ечишда, геометрик конфигурацияларда нуқталар бир –бири билан тўғри чизиқ ёки ёй билан бирлаштирилганми, буларнинг узунлиги қанча каби факторлар эътиборга олинмайди. Энг мухими шундаки, ҳар бир чизиқ қандайдир берилган иккита нуқтани бирлаштираяпти. Шундай қилиб, графнинг таърифини қуйидагича бериши мумкин.
Таъриф. Тўплам V={a₁,a₂,…,a_n} ва V тўпламдан олинган жуфтликлар E={(a_i1, a_j1),…,(a_ik, a_jk)} наборига Граф дейилади.
V тўпламдаги a₁,…,a_n лар қандайдир объектлар бўлиб Г графнинг учлари дейилади. Е тўпламдаги ҳар бир (a_i1, a_j1),…,(a_ik, a_jk) жуфтлик Графнинг қирралари дейилади.
Агар (a_i, a_j) қирра берилган бўлса, у ҳолда a_i, ва a_j учлар бирлаштирилган дейилади.
Мисол. Агар V={a₁, a₂, a₃, a₄, a₅, a₆, a₇,}ва E={(a₁,a₂)(a₂,a₂)(a₂,a₃)(a₃,a₄)(a₄,a₅)(a₅,a₆)(a₆,a₅)} бўлсин, у ҳолда V ва Е тўплам Г графни ҳосил қилади.
Графнинг учларини тугунлар, 2 та учини бирлаштирувчи чизиқни қирралар деб атаймиз.

Графнинг иккита тугуни умумий қирра билан ўзаро боғланган бœлса, улар қўшни тугунлар дейилади.

Агар Г нинг 2 та қирраси умумий тугунга эга бўлса, улар қўшма қирралар дейилади.
Мисол. (а₁ а₂) қирра ( а₂ а₃) қиррага қўшма,
чунки а₂ умумий тугунга эга.
Бирорта тугунни ўзини - ўзига боғлайдиган қиррага сиртмоқ дейилади.
Барча тугунлари ёлғиз тугундан иборат граф ноль (бўш) граф дейилади.

Агар Г графнинг барча тугунлари ўзаро боғланган бўлса, бундай граф тўлиқ граф дейилади.

А гар Г графнинг барча қирраларида йўналиш кўрсатилган бўлса, бундай граф йўналтириган граф дейилади.

Агар Г графнинг қирраларида йўналтириш кўрсатилмаган бўлса, у ќолда граф йўналтирилмаган граф дейилади.

в^| с^| d^|

в с d
Г^| граф Г графнинг қисми дейилади, агар Г^| нинг тугунлари тўплами Г га тегишли бўлса, яъни V^| V бўлса, ҳамда Г^| нинг барча қирралари Г нинг ҳам қирралар бўлса, яъни Е^| E

V={a, в, c, d}, V^|={a^|, b^|, c^|, d^|}, V^| V .

Г^/ Граф Г графнинг тўлдирувчиси дийилади, агарда унинг барча тугунлари Г графга тегишли бўлиб, бирорта ҳам қирраси Г га тегишли бўлмаса.