DISKREČIOSIOS STRUKTŪROS. KURSINIS DARBAS

Ištrauka

DISKREČIOSIOS STRUKTŪROS
KURSINIS DARBAS

Turinys
2. Užduotis B16 ........................................................................................................ 3
3. Užduoties analizė ................................................................................................. 3
4. Programos tekstas ............................................................................................... 4
5. Testavimo pavyzdžiai ........................................................................................... 7
PIRMAS TESTAS .................................................................................................................................... 7
ANTRAS TESTAS ................................................................................................................................... 8
TREČIAS TESTAS .................................................................................................................................. 9
6. Išvados ................................................................................................................ 9
7. Literatūros sąrašas .............................................................................................. 9

1. Užduotis B16

Parašyti programą, kuri patikrintu ar pografiai yra indukuoti ir rasti bendrą briaunų skaičių. 

2. Užduoties analizė 
Tarkime A yra grafo G viršūnių aibės V poaibis. Tada grafas P=(A,B) yra indukuotasis pografis,
kurį indukuoja viršūnių aibė A, jei jo viršūnių aibė sutampa su aibe A, o briaunų (lankų) aibę B sudaro tos
grafo G briaunos (lankai), kurių abu galai priklauso aibei A.
Uždavinys. 16. Duotas grafas G ir du jo pografiai G1 ir G2. Sudaryti programą, kuri nustatytų, ar
šie pografiai yra indukuoti, šių pografių bendrų briaunų skaičių.
Metodo idėja. Pirmiausia duoto grafo ir pografio masyvai yra išrikiuoti, kad viršuje skaičius būtu
mažesnis už apatinį. Tada viena iš funkcijų suranda visas galimas pografio briaunas pagal jo viršūnes.
Vėliau tos briaunos yra lyginamos su pačiu pografiu ir kurios nėra pografio briaunos yra dedamos į naują
masyvą. Naujas masyvas yra tikrinamas su duotu grafu ir jeigu grafo nors viena briauna sutampa su nauju
masyvų vadinasi, kad šis pografis nėra indukuotas. Tie patys žingsniai yra kartojami su kitu pografiu ir
pabaigoje randama jų bendra briaunų suma.