Diskrečiosios struktūros kursinis darbas

Duotas grafas G ir du jo pografiai G1 ir G2. Nustatyti, ar šie pografiai yra indukuoti, šių pografių bendrų briaunų skaičių.
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. Paprastai, indukuotasis pografis – tai toks pografis G1, kuris turi grafo G0 viršūnių poaibį ir visas galimas G0 briaunas.
Uždavinys. Duoti grafai G, G1, G2, kur visi grafai G = (V,U), kur n – grafo viršūnių skaičius ir m – grafo briaunų skaičius, V – viršūnių, o U – briaunų aibės. Patikrinti, ar grafo G pografiai G1 ir G2 yra indukuoti (grąžinti 1, jei taip arba grąžinti 0, jei ne). Taip pat suskaičiuoti, kiek bendrų briaunų m šie pografiai turi.
Metodo idėja. Panagrinėkime paprasčiausią pavyzdį. Įsivaizduokime grafą G, kuris turi viršūnes 1, 2 ir 3. Tai pilnasis grafas, t. y. jo kiekviena viršūnė yra sujungta su visomis likusiomis viršūnėmis. Šis grafas G turi 3 briaunas. Dabar paimkime pografį G1, kuris turi tik vieną vienintelę viršūnę nr. 1. Kadangi jo viršūnių aibė yra grafo G viršūnių poabis ir pografis G1 neturi jokių briaunų (nes neįmanoma), tai šis pografis yra indukuotasis. Dabar prie grafo pridėkime viršūnę nr. 2. Vėlgi turime tinkamas viršūnes, bet pografis neturi visų įmanomų grafo G briaunų, t. y. pografis G1 turėtų turėti briauną, jungiančią viršūnes nr. 1 ir 2. Šią briauną pridėjus, pografis G1 taptų indukuotas. Panagrinėkime tokią situaciją: pridėkime viršūnę nr. 4 į pografį G1. Nuo šio momento pografis G1 niekada nebus indukuotasis, kadangi jo viršūnių aibė nebėra grafo G viršūnių aibės poaibis.
Grafai yra aprašomi viršūnių masyvu ir briaunų matrica.
Pirmiausia bus tikrinama, ar pografiai yra indukuoti. Pirmiausia vyksta patikrinimas, ar pografio viršūnių aibė yra...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!