From Wikipedia, the free encyclopedia
Gráf je v matematiki struktura in predstavlja abstraktno upodobitev množice objektov, v kateri so nekateri pari objektov povezani z vezmi. Medsebojno povezani objekti so upodobljeni z matematičnimi abstrakcijami, imenovanimi točke (ali tudi vozlišča), vezi, ki povezujejo nekatere pare točk, pa se imenujejo povezave. Običajno je graf prikazan v diagramski obliki kot množica pik za točke, ki jih povezujejo daljice ali krivulje za povezave.
Povezave so lahko usmerjene (asimetrične) ali neusmerjene (simetrične). Če na primer točke prikazujejo ljudi na zabavi, in med dvema človekoma, ki se rokujeta, obstaja povezava, je to neusmerjeni graf, saj, če se oseba A rokuje z osebo B, se tudi oseba B rokuje z osebo A. Če na drugi strani točke predstavljajo ljudi na zabavi, in obstaja povezava od osebe A do osebe B, če oseba A pozna osebo B, je to usmerjeni graf, saj poznavanje nekoga ni nujno simetrična relacija, oziroma, če ena oseba pozna drugo osebo, obratno nujno ne velja. Mnogo oboževalcev lahko pozna znano osebo, malo pa je verjetno, da bo znana oseba poznala vse svoje oboževalce. V takšnem usmerjenem grafu so povezave usmerjene in se imenujejo tudi loki.
Besedo »graf« je v tem smislu prvi rabil James Joseph Sylvester leta 1878.[1]
Veja matematike in računalništva, ki raziskuje značilnosti grafov, se imenuje teorija grafov.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.