Algoritmica grafurilor - 10

Trimis la data: 2010-11-08 Materia: Inginerie Nivel: Facultate Pagini: 14 Nota: / 10 Downloads: 0
Autor: Oana_B Dimensiune: 42kb Voturi: Tipul fisierelor: doc Acorda si tu o nota acestui laborator: 1 2 3 4 5 6 7 8 9 10
vezi mai multe detalii vezi mai putine detalii
Raporteaza o eroare
Initial vom demonstra ca graful H obtinut este conex, si anume ca exista drum intre oricare 2 noduri ale sale.
Se observa ca in cazul multimilor de muchii ale arborilor partiali, cardinalul diferentei lor simetrice este numar par. Aceasta are loc intrucat multimile de muchii ale celor 2 arbori pentru care calculam diferenta simetrica au acelasi cardinal (arborii partiali ai unui graf au exact n-1 muchii). Deci daca un arbore difera de un al doilea printr-o muchie este evident ca si cel de-al doilea are o muchie diferita de cele ale primului.
Referate similare: Nu exista laboratoare similare

Acest lucru se poate demonstra prin reducere la absurd.
Presupunem prin reducere la absurd ca exista T1 si T2, 2 arbori partiali pentru un graf G, astfel incat |E(T1) E(T2)| = 2k + 1, k 0. Aceasta inseamna ca un arbore difera de celalalt printr-un numar par de muchii (sa zicem prin 2s muchii), iar celalalt arbore difera de primul printr-un numar impar de muchii (2t+1 muchii), astfel incat 2s+2t+1 = 2k+1.

Putem face presupunerea ca T1 difera de T2 prin 2s muchii. Deci restul muchiilor din T1, si anume n-1-2s, apar si in T2. Dar mai sus am obtinut ca T2 are 2t+1= 2k+1-2s muchii diferite de cele din T1. Deci T2 are 2k+1-2s+n-1-2s = n+2k-4s muchii. Stiam ca T2 are, asemenea tuturor arborilor partiali, n-1 muchii. Obtinem ca 4s-2k = 1, ceea ce este absurd, intrucat 4s-2k este numar par.
Asadar presupunerea initiala este falsa si deci putem spune ca |E(T1) E(T2)| = 2k, k>0 pentru oricare 2 arbori partiali T1 si T2.

Vom demonstra ca graful H este conex si are diametrul cel mult n - 1 prin inductie dupa cardinalul K = 2k al diferentei simetrice a multimilor de muchii.Pasul de baza:La acest pas vom verifica daca pentru oricare 2 arbori, pentru care diferenta simetrica dintre multimile lor de muchii are cardinalul 2, exista drum intre ei.
Din ipoteza stim ca intre doi arbori partiali care difera printr-o singura muchie exista muchie in graful H. Asadar exista drum intre oricare doi arbori partiali cu aceasta proprietate.

Vom demonstra ca si intre oricare doi arbori care difera prin k muchii (adica au cardinalul diferentei simetrice egal cu 2k) exista drum in graful H.
Pentru aceasta vom gasi un arbore partial T3 care difera prin k-1 muchii de T1 si printr-o muchie de T2. Daca reusim acest lucru, obtinem un drum de la T1 la T2 care trece prin T3 (stim, conform ipotezei inductive, ca exista drum de la T1 la T3, intrucat acestia difera prin k-1 muchii; intre T3 si T2AZAZAZAZAZ avem muchie in H, intrucat cei 2 arbori difera printr-o singura muchie).

  • pag. 1
  • pag. 2
  • pag. 3
  • pag. 4
  • pag. 5
  • pag. 6
  • pag. 7
  • pag. 8
  • pag. 9
  • pag. 10

Nota explicativa
Referatele si lucrarile oferite de Referate.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Referat.ro te invata cum sa faci o lucrare de nota 10!
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Filmulete haioase Filme, poante si cele mai tari faze Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10
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.
Confidentialitatea ta este importanta pentru noi

Referat.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat politica de confidentialitate pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles