| Title: | KARAKTERIZACIJA REDUCIBILNIH ŠESTKOTNIKOV ELEMENTARNIH BENZENOIDNIH GRAFOV |
|---|
| Authors: | ID Černel, Milan (Author)
ID Taranenko, Andrej (Mentor) More about this mentor...  |
|---|
| Files: |  UNI_Cernel_Milan_2011.pdf (582,11 KB)
MD5: BF60CAA3E4F6E609A98ABB11935DA25B
PID: 20.500.12556/dkum/5f098254-f859-45d9-b347-a09efac2e58c
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Undergraduate thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | Benzenoidni graf je končen povezan v ravnino vložen graf brez presečnih vozlišč, v katerem je vsako lice omejeno s pravilnim šestkotnikom z dolžino stranice ena. Benzenoidni graf G je elementaren, če vsaka povezava pripada nekemu 1-faktorju grafa G. Šestkotnik h elementarnega benzenoidnega grafa je reducibilen, če tudi po odstranitvi mejnih povezav in vozlišč tega šestkotnika, graf ostane elementaren benzenoidni graf. Karakteriziramo reducibilne šestkotnike elementarnega benzenoidnega grafa. Karakterizacija je osnova za algoritem, s katerim se ugotovi zaporedje reducibilnih šestkotnikov, ki dekompozirajo graf iz te družine, v času O(n2). Poleg tega je predstavljen algoritem, ki dekompozira elementarni benzenoidni graf z največ eno perikondenzirano komponento v linearnem času. |
|---|
| Keywords: | graf, vrh, dolina, lice, benzenoidni graf, 1-faktor, reducibilni šestkotnik, dekompozicija reducibilnih lic |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [M. Černel] |
|---|
| Year of publishing: | 2011 |
|---|
| PID: | 20.500.12556/DKUM-18256 |
|---|
| UDC: | 51(043.2) |
|---|
| COBISS.SI-ID: | 18406408 |
|---|
| NUK URN: | URN:SI:UM:DK:AQECPZFU |
|---|
| Publication date in DKUM: | 30.05.2011 |
|---|
| Views: | 2962 |
|---|
| Downloads: | 198 |
|---|
| Metadata: |    |
|---|
| Categories: | FNM
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
