Grafeo kun 6 verticoj kaj 7 lateroj

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.

Vidu ankaŭ

Eksteraj ligiloj

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.