loyihalash jarayonini avtomatlashtirishning graflar nazariyasi asoslari

DOC 138,5 КБ Бесплатная загрузка

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

$1403783388_47192.doc loyihalash jarayonini avtomatlashtirishning graflar nazariyasi asoslari ts larning konstruktsiyasini loyihalashda ts elementlarini nuqtalarda, elementlararo aloqalarini chiziqlarda ifodalab tuzilgan modellardan foydalanilsa loyihalash ishlari ancha engillashadi. eng asosiysi eò²m dan foydalanish uchun imkoniyat yaratiladi. matematikada oâzaro aloqada boâlgan, ikkita toâplamlardan tashkil topgan obâektlarga graflar deyiladi. grafning nuqtalar toâplamini x bilan belgilaydi va ularni uchlar toâplami deb ataydi x = {x1 x2,... ,xn}, /x/ = n ikkita qoâshni uchlarni birlashtiruvchi chiziqlar toâplamini u bilan belgilaydi va ularni tomonlar yoki yoylar deb ataydi u = {u1, u2 ,â¦un}, /x/ = n demak graf deb ikkita toâplamdan tashkil topgan quyidagi obâektga aytilar ekan g = (x u) (29) umuman olganda u lar toâplami quyidagicha boâlishi mumkin u = u u u (v - â«yokiâ» soâzi belgisi) bunda u - orientirlanmagan chiziqlar qism toâplami, yoki tomonlar qism toâplami. x1 va xj uchlarni birlashtiruvchi bunday tomonlar quyidagi shaklda ifodalanadi uk = (xi, xj) yoki uk=(xj, xi) …$

shaklidagi jadvalni intsidentlik matritsasi deb ataladi. 1, agar xk uchi u1 tomonga intsidentli boâlsa. 0, uch bilan tomon intsidentli boâlmasa 19-rasmdagi grafning intsidentlik matritsasi quyidagicha boâladi. [image: image5.wmf]1 1 0 0 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 x x x x j 6 5 4 3 2 1 4 3 2 1 u u u u u u = (31) matritsa qatorlari uchlarga ustunlari esa tomonlarga mos boâladi. grafda sirtmoqlar mavjud boâlsa mos ustunga 1 belgisi qoâyiladi. r va j matritsalar berilgan graflarni toâliq ifodalab beradi va shu sababli loyihalashni eò²m yordamda bajarishga koâpincha shunday formadagi graf modellaridan foydalaniladi. grafdagi qoâshni tomonlarning ketma-ketligi â¦,(x1 xj), (xj xk), (xk x1),â¦ marshrut deb ataladi. marshrutdagi tomonlar soni s uning uzuligi deyiladi. takrorlangan tomonlari yoâq marshrut tsep (zanjir), boshlanishi va oxiri bir uchga joylashgan berk konturli tsep esa tsikl …

deb ataladi va ðn bilan belgilanadi. toâla graflarda albatta gamilñton-tsikl mavjud boâladi. 20-rasmdagi ikkali graf ham toâla graflar boâlganligi uchun ularda gamilñton-tsikli mavjud (gtts=(x1, x2, x3, x4, x5, x6)). ð¦iklga ega boâlmagan graflar daraxt deb ataladi va 'g harfida belgilanadi. har qanday daraxt n-1 tomonga ega boâladi. boshlangâich bu grafda /x/=5, /u/=13, u=u u u; u={u1 u6 u13} u={u3 u4 u5 u6 u7 u8 u9 u11}; u={u2 u10 u13}; barcha tomonlari orientirlangan graflar orgraflar, orientirlanmagan graflar esa neograflar deb ataladi. avvalo faqat neograflarni koârib chiqamiz va qulayroq, boâlishi uchun ularni umulashgan nom bilan graflar deb nomlaymiz. birorta ikki uchini tutashtiruvchi m ta tomonlari bor graflarga mulñtigraflar deyiladi. maksimal m esa grafning multisoni deb ataladi. 21-rasmda multisoni m=5 ga teng mulñtigraf misoli koârsatilgan. [image: image8] 21-rasm.mulñtigraf misoliga doir. agar grafning biror uk tomoni xi va xj uchlarini tutashtirgan boâlsa uk tomoni xi va xj uchlariga intsidentli deb ataladi, yoki xi va …

j, uchlari m ta tomonlar bilan qoâshni boâlsa, rij=0, agar ular oâzaro òoâshni boâlmasa. misol uchun 19-rasmdagi geometrik formada tasvirlangan grafning qoâshnichilik matritsasini tuzaylik: uchni ildiz, undan chiqqan tomonlarni esa, shoxlar(tarmoqlar) deb ataydi. 22-rasmda daraxt-grafning geometrik tasviri misoli keltirilgan [image: image9] 22-rasm. daraxt-grafining misoliga doir. grafdagi ikki uchlarni tutashtiruvchi eng kam tomonlarning soni (eng qisqa tsep uzunligi) masofa deb ataladi va dij da belgilanadi. graf uchun masofa funktsiyasini masofa matritsasida ifodalash qulaydir (d=dij) va bu matritsa elementlari (kataklari) qoâyidagi qoidaga asosan aniqlanadi: 20-rasmdagi graf uchun masofa matritsasi quyidagicha boâladi: [image: image10.wmf]0 1 1 2 1 1 1 0 1 2 2 2 1 1 0 1 1 2 2 2 1 0 1 2 1 2 1 1 0 1 1 2 2 2 1 0 6 5 4 3 2 1 6 5 4 3 2 1 x x x x x x x x x x x x …

1617382.unknown _1231622868.unknown _1255515914.unknown _1231619195.unknown _1231616118.unknown

Хотите читать дальше?

Скачайте полный файл бесплатно через Telegram.

Скачать полный файл

О "loyihalash jarayonini avtomatlashtirishning graflar nazariyasi asoslari"

1403783388_47192.doc loyihalash jarayonini avtomatlashtirishning graflar nazariyasi asoslari ts larning konstruktsiyasini loyihalashda ts elementlarini nuqtalarda, elementlararo aloqalarini chiziqlarda ifodalab tuzilgan modellardan foydalanilsa loyihalash ishlari ancha engillashadi. eng asosiysi eò²m dan foydalanish uchun imkoniyat yaratiladi. matematikada oâzaro aloqada boâlgan, ikkita toâplamlardan tashkil topgan obâektlarga graflar deyiladi. grafning nuqtalar toâplamini x bilan belgilaydi va ularni uchlar toâplami deb ataydi x = {x1 x2,... ,xn}, /x/ = n ikkita qoâshni uchlarni birlashtiruvchi chiziqlar toâplamini u bilan belgilaydi va ularni tomonlar yoki yoylar deb ataydi u = {u1, u2 ,â¦un}, /x/ = n demak graf deb ikkita toâplamdan tashkil topgan quyidagi obâektga ...

Формат DOC, 138,5 КБ. Чтобы скачать "loyihalash jarayonini avtomatlashtirishning graflar nazariyasi asoslari", нажмите кнопку Telegram слева.

Теги: loyihalash jarayonini avtomatla… DOC Бесплатная загрузка Telegram