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



Download 324,5 Kb.
bet1/2
Sana28.04.2022
Hajmi324,5 Kb.
#586342
  1   2
Bog'liq
graflar

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


REJA:



  1. Графлар назарияси

  2. Қўшмалик матрицаси.

3. Қўшнилик матрицаси.
4. Эйлер графи.
5 Гамильтон графи

1. Графлар назарияси фани – чизиқлар ва нуқталардан тузилган баьзи бир геометрик конфигурациялар тўғрисидаги масалаларни ечишда ишлатилади. Бундай масалаларни ечишда, геометрик конфигурацияларда нуқталар бир –бири билан тўғри чизиқ ёки ёй билан бирлаштирилганми, буларнинг узунлиги қанча каби факторлар эътиборга олинмайди. Энг мухими шундаки, ҳар бир чизиқ қандайдир берилган иккита нуқтани бирлаштираяпти. Шундай қилиб, графнинг таърифини қуйидагича бериши мумкин.
Таъриф. Тўплам V={a1,a2,…,an} ва V тўпламдан олинган жуфтликлар E={(ai1, aj1),…,(aik, ajk)} наборига Граф дейилади.
V тўпламдаги a1,…,an лар қандайдир объектлар бўлиб Г графнинг учлари дейилади. Е тўпламдаги ҳар бир (ai1, aj1),…,(aik, ajk) жуфтлик Графнинг қирралари дейилади.
Агар (ai, aj) қирра берилган бўлса, у ҳолда ai, ва aj учлар бирлаштирилган дейилади.
Мисол. Агар V={a1, a2, a3, a4, a5, a6, a7,}ва E={(a1,a2)(a2,a2)(a2,a3)(a3,a4)(a4,a5)(a5,a6)(a6,a5)} бўлсин, у ҳолда V ва Е тўплам Г графни ҳосил қилади.
Графнинг учларини тугунлар, 2 та учини бирлаштирувчи чизиқни қирралар деб атаймиз.

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


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

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



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


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

в| с| d|



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

ҳамда Г| нинг барча қирралари Г нинг ҳам қирралар бўлса, яъни Е| E


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


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




Download 324,5 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish