| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 2 / 2
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Vozliščno pokritje k-poti v grafih
Igor Jesih, 2013, diplomsko delo

Opis: Diplomsko delo obravnava vozliščno pokritje k-poti v grafih. Na začetku so predstavljeni osnovni pojmi teorije grafov, ki so potrebni za razumevanje nadaljne snovi. V nalogo so vključeni pojmi NP-polnost, regularni grafi in drevesa. Konec pa vključuje vozliščna pokritja k-poti za nekatere grafovske produkte. 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: Vozliščno pokritje, NP-polnost, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt.
Objavljeno: 22.04.2013; Ogledov: 1141; Prenosov: 131
.pdf Celotno besedilo (287,73 KB)

2.
Minimum k-path vertex cover
Boštjan Brešar, František Kardoš, Ján Katrenič, Gabriel Semanišin, 2011, izvirni znanstveni članek

Opis: Podmnožica ▫$S$▫ množice vozlišč grafa ▫$G$▫ se imenuje po poteh ▫$k$▫-vozliščno pokritje, če vsaka pot reda ▫$k$▫ v grafu ▫$G$▫ vsebuje vsaj eno vozlišče iz ▫$S$▫. Označimo s ▫$psi_k(G)$▫ najmanjšo kardinalnost po poteh ▫$k$▫-vozliščnega pokritja v grafu ▫$G$▫. V članku dokažemo, da je problem določitve ▫$psi_k(G)$▫ NP-poln problem za vsak ▫$k geq 2$▫, medtem ko lahko za drevesa ta problem rešimo v linearnem času. Raziskujemo zgornje meje za vrednost ▫$psi_k(G)$▫ in dokažemo več ocen ter točnih vrednosti za to število. Prav tako dokažemo, da je ▫$psi_3(G) leq (2n + m)/6$▫, za vsak graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami.
Ključne besede: matematika, teorija grafov, algoritem, vozliščno pokritje, pot, NP-polnost, disociacijsko število, po poteh vozliščno pokritje, mathematics, graph theory, algorithm, path, vertex cover, dissociation number, path vertex cover, NP-complete
Objavljeno: 10.07.2015; Ogledov: 365; Prenosov: 4
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.07 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici