diplomsko delo
Povzetek
Diplomsko delo obravnava vozliščno pokritje k-poti v grafih. Na začetku so predstavljeni osnovni pojmi teorije grafov, ki so potrebni za razumevanje nadaljnje snovi. V diplomsko delo so vključeni pojmi NP-polnost, regularni grafi in drevesa. Konec pa vključuje vozliščna pokritja k-poti za nekatere produkte grafov. Za velikost najmanjšega vozliščnega pokritja glede na stopnjo vozlišča bodo določene zgornje in spodnje meje grafa. Izboljšani bosta zgornja in spodnja ocena za najmanjše možno število vozlišč v pokritju k-poti pri kartezičnem, krepkem in leksikografskem produktu.
Ključne besede
matematika;vozliščno pokritje;teorija grafov;regularni grafi;kartezični produkti;krepki produkti;leksikografski produkti;NP-polnost;diplomska dela;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2013 |
Tipologija: |
2.11 - Diplomsko delo |
Organizacija: |
UM FNM - Fakulteta za naravoslovje in matematiko |
Založnik: |
[I. Jesih] |
UDK: |
519.17(043.2) |
COBISS: |
19825928
|
Št. ogledov: |
1631 |
Št. prenosov: |
164 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
The k-path vertex cover of graphs |
Sekundarni povzetek: |
The diploma thesis deals with the k-path vertex cover of graphs. In the beginning, we will present the basic concepts of graph theory which are essential for further understanding of the subject. There are concepts of NP-completeness, regular graphs, and trees involved in the thesis. In the conclusion the k-path vertex cover of some graph products is determined. For the minimum k-path vertex cover we will determine some lower and upper bounds of graphs in respect to its degree. Lower and upper bounds for the minimum k-path vertex cover of the Cartesian product, the strong product, and the lexicographic product will also be improved. |
Sekundarne ključne besede: |
Vertex cover;NP-completeness;regular graphs;the Cartesian product;the strong product;the lexicographic product.; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Diplomsko delo |
Komentar na gradivo: |
Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo |
Strani: |
42 f. |
ID: |
8726054 |