Vertico (grafeoteorio)

En grafeoteorio, vertico estas la fundamenta unuo el kiuj grafeoj estas formitaj: sendirekta grafeo konsistas el aro de verticoj kaj aro de lateroj (neordigitaj paroj de verticoj), kaj orientita grafeo konsistas el aro de verticoj kaj aro de arkoj (ordigitaj duopoj de verticoj). De vidpunkto de grafeiteorio, vertico estas traktata kiel senpropraĵa kaj nedividebla objekto.

Vertico w estas najbara al alia vertico v se la grafeo enhavas lateron (v, w). La najbaraĵo de vertico v estas konkludita subgrafeo de la grafeo, formita per ĉiuj verticoj najbaraj al v.

La grado de vertico en grafeo estas la kvanto de lateroj incida al ĝi. Izola vertico estas vertico kun grada 0. Folia vertico estas vertico kun grado 1. En orientita grafeo, oni povas distingi la eksterengradon (kvanto de elirantaj lateroj) kaj la enengradon (kvanto de alirantaj lateroj); fonta vertico estas vertico kun enengrado 0, lavuja vertico estas vertico kun eksterengrado 0.

Grafeo estas vertico-transitiva, se ĝi havas simetriojn kiuj ĵetas ĉiun verticon al ĉiu alia vertico. En la ĉirkaŭteksto degrafnumerado kaj grafea izomorfio gravas distingi inter markitaj verticoj kaj nemarkitaj verticoj. Markita vertico estas vertico, kiu estas identigita per markilo ebliganta distingi ĝin de la aliaj markitaj verticoj; du grafeoj povas esti konsiderataj izomorfaj, se ili efektivigas rilatojn nur inter paroj de verticoj kun egalaj markiloj. Nemarkita vertico estas tia, kiu povas esti anstataŭigita per ĉiu la alia vertico nur surbaze de ĝia konekteco en la grafeo.