Plokštieji grafai

Grafas – figūra, sudaryta iš taškų (vadinamų viršūnėmis) ir iš atkarpų, jungiančių kai kurias iš šių viršūnių.
F su A, B, D, E ir C.
Kiekvieną komandą žymime tašku (skrituliuku) ir kiekvienus du taškus, kurie atitinka žaidusias tarpusavyje komandas, sujungiame atkarpa. Šitokia schema vadinama grafu (1* pav).
Grafo viršūnė – kurios nors grafo briaunos galas.
Pvz.: 1* paveikslėlyje grafo briaunos (A,F) viršūnės yra A ir F.
Grafo briauna – kreivė, kuri jungia dvi grafo viršūnes.
Pvz.: 1* paveikslėlyje grafo viršūnės yra B ir C, o jas jungianti kreivė (B,C) – grafo briauna.
Izomorfiniai grafai – tai grafai, pvz.: G1 ir G2 , tarp kurių viršūnių galime nustatyti tokią abipus vienareikšmę atitinkamybę, kad dvi bet kurios grafo G1 viršūnės būtų sujungtos briauna tada ir tik tada, kai jas atitinkančios grafo G2 viršūnės yra sujungtos briauna.
Pvz.:
Grafo praplėtimas – operacija, kurios metu iš vienos briaunos padaromos kelios.
Pvz.: Grafo G1 briaunose (A,B) ir (B,C) pažymėjome naujas viršūnes a, b, c ir d. Dabar šios briaunos yra sudarytos iš kelių briaunų: (A,B) iš (A, a), (a,b) ir (b,B); (B,C) iš (B,c), (c,d) ir (d,C). Taigi grafas G1 praplečiamas iki grafo G2.
Grafo sutraukimas – operacija, kurios metu iš kelių briaunų padarome vieną (veiksmas, atvirkščias grafo praplėtimui). Analogiškai viskas vyksta ir su grafo viršūnių, bei briaunų sutraukimu.
Pvz.: Pažiūrėkime 2* pav. Turime grafą G2, kurio briaunos yra sudarytos iš kelių briaunų: (A,B) iš (A, a), (a,b) ir (b,B); (B,C) iš (B,c), (c,d) ir (d,C). Šį grafą galime sutraukti iki grafo G1, pašalinant tarpines viršūnes a, b iš briaunos (A,B) ir c, d iš briaunos (C,D).
Grandinė – linija grafe, kuri nė viena briauna neina daugiau kaip vieną kartą.
Pvz.: 3*pav. grandinę sudaro briaunos:
Ciklas – uždara grandinė.
Pvz.: 2*paveikslėlyje G1 grafe ciklą sudaro grandinė: (A,B), (B,C), (C,D), (D,A).
Grafo siena – tai plokštumos dalis, apribota ciklu, kurioje nėra nei viršūnės, nei briaunos.
Pvz.: 4*paveikslėlyje ,,I“ plokštumos
Minimalusis ciklas – ciklas, ribojantis grafo...

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!