Teorija grafova - problem uparivanja | seminarski diplomski

Ovo je pregled DELA TEKSTA rada na temu "Teorija grafova - problem uparivanja". Rad ima 17 strana. Ovde je prikazano oko 500 reči izdvojenih iz rada.
Napomena: Rad koji dobjate na e-mail ne izgleda ovako, ovo je samo DEO TEKSTA izvučen iz rada, da bi se video stil pisanja. Radovi koje dobijate na e-mail su uređeni (formatirani) po svim standardima. U tekstu ispod su namerno izostavljeni pojedini segmenti.
Uputstvo o načinu preuzimanja rada možete pročitati OVDE.

SADRŽAJ
1. Uvod 1
2. Osnovni pojmovi u teoriji grafova 2
3. Uparivanje u grafu (osnovni pojmovi) 4
4. Maksimalna kardinalnost uparivanja u bipartitnim grafovima 5
5. Minimalno težinsko uparivanje u bipartitnom grafu 8
6. Savršeno uparivanje u gustim grafovima 11
7. Maksimalna kardinalnost uparivanja u opštim grafovima 12
LITERATURA 16
Uvod
Teorija grafova je jedna od najmlađih i najnaprednijih grana u matematici. Popularnost teorije grafova leži isključivo u velikoj primjeni u računarskim naukama. Činjenica je da se veliko bogatstvo teorije grafova nije dogodilo sve do ekspanzije kompjutera pre nekih pedeset godina. Sadržaj ovog seminarskog rada je prilično interesantan problem u teoriji grafova, a govori o pronalaženju različitih uparivanja u raznim grafovima. Uparivanja su uopšteno do skoro bila predmet važnih istraživanja, kako često nalaze primjenu u problemima realnog svij eta. Generalan princip uparivanja je sledeći: dat je graf, treba naći što je više moguće nezavisnih ivica (edges), tako da je neki globalni kriterijum zadovoljen, ili preciznije, tako da je nešto ekstremno.
Uparivanje u grafu je skup ivica od kojih nijedne dvij e nemaju nijedan zajednički čvor. Ovdje ćemo diskutovati o teorijskoj osnovi i aktuelnoj algoritamskoj implementaciji za nalaženje maksimalne kardinalnosti i težinskog uparivanja u bipartitnom grafu, isto kao i nalaženje maksimalne kardinalnosti uparivanja u gustom i opštem grafu.
Osnovni pojmovi u teoriji grafova
Graf predstavlja uređeni skup, gdj e je skup č vorova (vertices), a skup ivica (edges), u kome svaka ivica predstavlja par č vorova iz . Kaž emo da su dva čvora susjedna (adjacent) ako i samo ako postoji ivica koja ih spaja, i takođ e da je čvor susedan (incident) ivici ako i samo ako je jedan od č vorova spojenih ivicom . Broj ivica koje su susjedne sa neki m č vorom je stepen (degree) tog č vora. Svi čvorovi koji su susj edni nekom čvoru se nazivaju susj edima (neighbors) . Skup svih susj eda nekog č vora obilježava se sa . Za neki podskup , definišemo . Ivica koja spaja neki č vor sa samim sobom zove se petlja (loop). Prost graf je graf koji nema ni petlji ni viš estrukih ivica, što znač i da nijedna dva čvora nisu spojena sa viš e od jednom ivicom.
Graf može biti neusmjeren (undirected) ili usmjeren (directed), kod koga svaka ivica ima i svoj smjer (znač i ako je povezano sa , ne mora biti i da je povezano sa ). Takođe, graf može biti i težinski (weighted) ako svaka ivica ima sebi dodeljenu neku vrijednost (težinu). I netežinski graf može se posmatrati kao tež inski, s tim što bi težina svake ivice bila jednaka (recimo 1). Zato u daljem tekstu nećemo navoditi eksplicno da li je graf tež inski ili ne, ukoliko to nije bitno za sam algoritam.
...

CEO RAD MOŽETE PREUZETI NA SAJTU: WWW.MATURSKIRADOVI.NET