Alternating plane graphs

angleški

2015

letnik 8, številka 2

alternirajoče stopnje   hevristično iskanje   izčrpno iskanje   ravninski grafi

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Ravninski graf se imenuje alternirajoč, če imajo vsa sosednja vozlišča različne stopnje, prav tako pa tudi vsa sosednja lica. Alternirajoče ravninske grafe so prvič obravnavali leta 2008. Ta članek povzema dosedanje raziskave o alternirajočih ravninskih grafih. Obstajata dva najmanjša alternirajoča ravninska grafa, vsak od njiju ima po 17 vozlič in 17 lic. Ni nobenega alternirajočega ravninskega grafa na 18 vozliščih, obstajajo pa alternirajoči ravninski grafi za vse grafe na 19 ali več vozliščih. Iz majhne množice začetnih gradnikov lahko konstruiramo alternirajoče ravninske grafe za vse grafe večjih redov. Veliko majhnih alternirajočih ravninskih grafov so našli z izdatno pomočjo računalnikov. V članek so vključeni teoretični rezultati o alternirajočih ravninskih grafih, v katerih so vse stopnje vozlišč elementi množice ?$\{3,4,5\}$?. Predstavljenih je tudi več razredov "šibko alternirajočih ravninskih grafov" (z vozlišči stopnje 2).

29.05.2020