Grafuri neorientate

Trimis la data: 2015-11-02
Materia: Matematica
Nivel: Liceu
Pagini: 13
Nota: 9.38 / 10
Downloads: 0
Autor: Rafael_B
Dimensiune: 40kb
Voturi: 1
Tipul fisierelor: doc
Acorda si tu o nota acestui referat:
Graf = orice multime finita V prevazuta cu o relatie binara interna E. Notam graful cu G=(V, E).

Graf neorientat = un graf G=(V, E) in care relatia binara este simetrica: (v,w)IE atunci (w,v) IE.

Nod = element al multimii V, unde G=(V, E) este un graf neorientat.

Muchie = element al multimii E ce descrie o relatie existenta intre doua varfuri din V, unde G=(V, E) este un graf neorientat;
Adiacenta: Intr-un graf neorientat existenta muchiei (v,w) presupune ca w este adiacent cu v si v adiacent cu w.
In exemplul din figura de mai sus varful 1 este adiacent cu 4 dar 1 si 3 nu reprezinta o pereche de varfuri adiacente.
Incidenta = o muchie este incidenta cu un nod daca il are pe acesta ca extremitate. Muchia (v,w) este incidenta in nodul v respectiv w.
Grad = Gradul unui nod v, dintr-un graf neorientat, este un numar natural ce reprezinta numarul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv)

Nod izolat = Un nod cu gradul 0.
Nod terminal= un nod cu gradul 1
Problema 1
Se citeste un graf din fisierul graf.txt: numarul de noduri, numarul de muchii si muchiile.
a) sa se afiseze matricea de adiacente
b) Sa se determine gradul unui nod citit
c) Sa se afiseze pentru un nod citit nodurile adiacente
d) sa se afiseze nodurile incidente cu cea de a x muchie din matrice
e) sa se afiseze pentru fiecare nod gradul
f) sa se afiseze nodul (nodurile) avand cei mai multi vecini
g) sa se afiseze nodurile izolate

Problema 2
Sa se det daca o matrice citita dintr-un fisier poate fi matricea unui graf neorientat. In caz afirmativ se va determina cate muchii are graful

Problema 3
Sa se genereze un graf avand maxim n noduri si maxim m muchii. Sa se afiseze matricea atasata
Observatie: graful nu poate fi decat cel mult complet
Home | Termeni si conditii | Politica de confidentialitate | Cookies | Help (F.A.Q.) | Contact | Publicitate
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.