Produkt grafova

završni rad

• Naslov (engleski): Graph product
• Autor: Fran Pećnjak
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Domagoj Kovačević (član povjerenstva)
• Član povjerenstva: Iva Manojlović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-06-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Ovaj rad bavi se s četiri osnovna produkta grafova: Kartezijev, jaki, tenzorski i leksikografski produkt. Razmatraju se njihova svojstva, odnosi i sličnosti s grafovima od kojih su nastali. Predstavljene su faktorizacije navedenih produkata i poznati rezultati. Posebna je pozornost dana bojanju produkata i povezanim problemima. Jedan od tih problema je Hedeteniemieva slutnja o kromatskom broju tenzorskih produkata. Izrađena je interaktivna web aplikacija za računanje i bojanje tenzorskih produkata koja koristi Hedeteniemievu slutnju za optimizaciju algoritma bojanja produkata.

Sažetak (engleski)

This thesis focuses on four most common products of graphs: Cartesian, strong, tensor and lexicographic product. Properties, relationships and similarities with graphs from which they were created are discussed. Prime factor decompositions and known results are presented. Particular attention is given to product colorings and related problems. One of these problems being Hedeteniemi's conjecture about chromatic number of tensor products. An Interactive web application for computing and coloring tensor products has been developed. Using knowledge and results of Hedeteniemi's conjecture, application optimizes product coloring algorithm.

• Ključne riječi: produkt grafova; tenzorski produkt; Kartezijev produkt; jaki produkt; leksikografski produkt; Hedeteniemieva slutnja; faktorizacija produkta; bojanje produkta grafova
• Ključne riječi (engleski): graph product; tensor product; Cartesian product; strong product; lexicographic product; Hedeteniemis conjecture; product factorisations; coloring graph product
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:696778
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2025-02-25 13:42:14