Teorija grafova

teorija grafova - to je jedan od podsekcije matematike, glavna karakteristika koja je geometrijska metoda u proučavanju objektima. Smatra se da je osnivač poznatog matematičara Euler.

Primjenu teorije grafova do kraja 19. stoljeća, sveden je na rješavanje zanimljivih problema i privukla veliku pažnju javnosti. Počevši od 20. stoljeća, kada je formirana teorije grafova kao samostalne matematička disciplina, to je naširoko koristi u oblastima kao što su kibernetiku, fizika, logistike, programiranje, biologije, elektronike, transport i komunikacije.

Osnovni pojmovi teorije grafova

Osnovica je grafikon. Terminologija se može naći takva stvar kao mreža identična kolone. Zadnje - je ne-prazna broj bodova, to jest, tjemena i duži, odnosno rebara, oba kraja koje odgovaraju dati broj bodova. teorija grafova ne ulaže određene tačke u vrijednosti od rubova i vrhova. Na primjer, gradskih prometnica i njihovo povezivanje, gdje je prva - temena grafikona, a drugi - rebra. Veći značaj se daje teoriju lukova. Ako su ivice imaju pravac, to se zove luk, ako grafikon sa usmjerenim granama, to se zove grafa.

U terminologiji teorije kao što su sljedeći pojmovi:

Podgrafu je graf, sve ivice i temena su među vrhova i rubova.

Povezani graf - onaj koji ima dva različita vrha postoji lanac ih povezuje.

Ponderirana povezan graf - onaj koji podesite funkciju pondera.

Tree - povezan graf bez ciklusa.

Kostur - podgraf koji je stablo.

Na grafikonu sliku u avionu definiran notacija koristi se: izabrane Vertex trenutku odgovara osnovnoj površini i ako rub je između čvorova, odgovarajuće tačke u kombinaciji segmentu. Ako je graf-orijentiran, ovi segmenti zamjenjuju se strelicama.

Ali ne porede grafikonu sliku s njim, odnosno sa apstraktne strukture, jer je jedan grafikon može se dati više od jednog grafički prikaz. Oslanjajući se na avion se daje kako bi vidjeti što par vrhova ujedinjeni rubova, a koji nisu.

Među neke od zadataka teorije grafova razlikovati:

1. Problem najkraćeg spoja (zamjena hardvera, plasman, ambulanta i telefonske centrale).
2. Maksimalni problem protoka (naručivanje pokret u dinamičnom mreže, distribuciju rada, organizaciji kapaciteta).
3. Problem premaza i paketa (smještaj otpremanje centri).
4. Bojenje u kolonama (memorija plasman na elektronskih računara).
5. Komunikacijske mreže i grafikoni (stvaranje komunikacijske mreže, analiza komunikacijskih mreža).

U ovom trenutku nije moguće programirati većina zadataka bez znanja teorije grafova. To olakšava i lakše raditi s kompjuterima.

Program koristi različite strukture i univerzalne metode za rješavanje problema, a jedan od njih je i teorija grafova. Njegova važnost se teško mogu precijenjena. teorija grafova u programiranju omogućava pojednostaviti potragu za informacijama, za optimizaciju softver, pretvoriti i distribuciju podataka. Kroz teoriju algoritama javlja mogućnost njihovog korištenja u ocjene za posebne poslove izvrši izmjene algoritma, bez smanjenja stepen pouzdanosti matematičkih konačnih verzija programa.

Važna karakteristika sistema kontrole ili model je skup binarnih odnosa s skup radnji i jedinica podataka. Ove strukture su samo dio programa i informacija je transformiran od njih. Stoga, grafikoni se baziraju na dizajn za programera.