Točka (teorija grafov)

Tóčka (vozlíšče ali vôzel) je v teoriji grafov osnovna enota, iz katere so sestavljeni grafi. Neusmerjene grafe sestavljata množica točk in množica povezav (neurejene pare točk), usmerjene grafe pa sestavljata množica točk in množica lokov (urejenih parov točk). Iz zornega kota teorije grafov se točke obravnavajo kot brezoblični in nedeljivi objekti, čeprav imajo lahko dodatno zgradbo, kar je odvisno od uporabe v kateri se pojavlja graf. Semantična mreža je na primer graf v katerem točke predstavljajo koncepte ali razrede objektov.

Izolirana točka predstavlja tudi polni graf ${\displaystyle K_{1}}$ (prazni graf ${\displaystyle N_{1}}$)

Dve točki, ki tvorita povezavo, sta njeni končni točki, povezava pa vodi v njiju - je incidenčna z njima. Točka w je sosedna drugi točki v, če graf vsebuje povezavo (v,w). Okolica točke v je inducirani podgraf grafa, nastal na vseh točkah, sosednih točki v.

Stopnja točke v grafu je število povezav incidenčnih z njo. Izolirana točka je točka s stopnjo 0, in ni končna točka nobene povezave. Hkrati predstavlja polni graf ${\displaystyle K_{1}}$, ki se imenuje prazni graf ${\displaystyle N_{1}}$. List (tudi pendantna točka) je točka s stopnjo 1.

V usmerjenem grafu je treba ločiti med izhodno stopnjo (število odhajajočih povezav) in vhodno stopnjo (število prihajajočih povezav). Izvirna točka je točka z izhodno stopnjo 0, ponirna točka pa je točka z vhodno stopnjo 0.

Točke v grafih ustrezajo ogliščem poliedrov, vendar jim niso enake. Skelet poliedra tvori graf, katerega točke so njegova oglišča, poliedrska oglišča pa imajo dodatno značilnost (svojo geometrijsko lego), ki se v grafih ne pojavlja. Ogliščna figura oglišča v poliedru predstavlja okolico točke v grafu.

Viri

• Berge, Claude (1958). Théorie des graphes et ses applications. Pariz: Collection Universitaire de Mathématiques, II Dunod. str. viii+277 pp. (angleška izdaja, Wiley 1961; Methuen & Co, New York 1962; ruska izdaja, Moskva 1961; španska izdaja, Mehika 1962; romunska izdaja, Bukarešta 1969; kitajska izdaja, Šanghaj 1963; druga izdaja prve angleške izdaje iz 1962. Dover, New York 2001)
• Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9.
• Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
• Gallo, Giorgio; Pallotino, Stefano (december 1988). »Shortest Path Algorithms« (PDF). Annals of Operations Research. Zv. 13, št. 1. Nizozemska: Springer. str. 1–79. doi:10.1007/BF02288320. Pridobljeno 18. junija 2008.{{navedi revijo}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)^{[mrtva povezava]}
• Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
• Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York: Academic Press. ISBN 0-12-324245-2.

Zunanje povezave

• Weisstein, Eric Wolfgang. »Graph Vertex«. MathWorld.