Izboljševanje zgornjih mej za problem največje klike z uporabo redukcijskih pravilKrpan, Aljaž (Avtor) Povh, Janez (Mentor) problem največje klikezgornje mejeredukcijerazcep na jedrarazcep na paličjastrukcijatestni primeri DIMACSV tem delu preučujemo povezavo med redukcijskimi pravili in funkcijami zgornje meje za problem največje klike. Pokažemo, kako lahko funkcije zgornje meje okrepijo klasični redukciji z jedri in paličji, če lokalne pogoje o velikosti nadomestimo z izračuni zgornje meje. Tako dobimo $(k,\omega^u)$-jedro in $(k,\omega^u)$-paličje, uvedemo pa tudi splošnejšo različico, imenovano $(k,d,\omega^u)$-paličje, pri kateri parameter $d$ določa razmerje med močnejšimi redukcijami in dodatnim računskim časom. Za vse te pojme dokažemo lastnosti ohranjanja klik, pravilnost pripadajočih algoritmov in njihovo časovno zahtevnost. Na podlagi teh redukcij uvedemo splošno ogrodje za izboljševanje zgornjih mej pri problemu največje klike. Predstavimo dve konkretni izvedbi ogrodja: prva uporablja združeni redukciji s paličji in jedri, druga pa ju dopolni s ponavljajočo se uporabo strukcije. Računski poskusi na 73 testnih grafih pokažejo, da lahko predlagane redukcije bistveno izboljšajo več standardnih funkcij zgornje meje in da je združevanje različnih redukcijskih metod v praksi koristno. Kombinacija strukcije ter redukcij s paličji in jedri je ob uporabi meje na podlagi algoritma DSatur pogosto dosegla vrednosti na ravni semidefinitnega programiranja hitreje kot neposredni izračun semidefinitne meje; pri testiranih grafih z gostoto povezav pod 0,7 je bila hitrejša v vsakem primeru. Z uporabo redukcije s paličji in jedri ter Lovászeve funkcije theta izboljšamo tudi doslej najboljše certificirane celoštevilske zgornje meje za tri zahtevne primere DIMACS, katerih natančna klična števila niso znana: za graf C500.9 s 83 na 73, za graf C1000.9 s 122 na 115 in za graf C2000.9 s 177 na 168.20262026-09-24 08:15:32Magistrsko delo/naloga188557sl