Jurij Kovič: Maksimalna in minimalna energija grafov, 2. del

Povzetek:

1. Umestitev problema v kontekst sorodnih problemov: problem iskanja maksimalne in minimalne "energije" oštevilčenih grafov, ki je bil predstavljen na enem od prejšnjih seminarjev, sodi v veliko družino problemov v zvezi z oštevilčenimi grafi, ki pa se ukvarjajo z drugimi vidiki oštevilčenih grafov.
2. Reformulacija oziroma ostrejša formulacija problema: v 1.delu smo govorili o razmeroma širokem problemu: kako porazdeliti dano množico nenegativnih števil po točkah danega grafa tako, da bo vsota produktov teh števil, prirejena sosednjim točkam grafa, maksimalna (ali pa minimalna). Videli smo, da je ta problem v splošnem težak. Tokrat bomo obravnavali poseben primer, in sicer bomo točkam grafa z n točkami priredili različna naravna števila 1,2,...,n.
3. Definicija "energije" grafa: Če vpeljemo pojem energije oštevilčenega grafa kot vsote produktov števil 1,2,...,n, prirejenih sosednjim točkam grafa, potem sta maksimalna in minimalna energija danega grafa (po vseh možnih oštevilčenjih n točk grafa s števili 1,2,...,n) invarianti grafa. Zdaj se naravno zastavi vprašanje, kako izračunati to varianto (ali jo vsaj oceniti navzgor (za maksimume) oziroma navzdol (za minimume) za posamezne grafe ali družine grafov.
4. Pregled nekaj konkretnih izračunov maksimalnih in minimalnih energij: Videli bomo, kako lahko izračunamo ali vsaj ocenimo maksimalne in minimalne energije določenih grafov in razredov grafov.
5. Ovrednotenje izračunov predvsem v smislu dveh odprtih vprašanj: (i) ali oziroma na kakšen način bi se dalo za dobljene ocene morda dalo preveriti, ali predstavljajo natančne zgornje ali spodnje meje (ii) ali bi lahko dobljene invariante (maksimalne oziroma minimalne energije grafov) lahko kaj pripomogle k problemu klasifikacije grafov?

Vabljeni!