Граф (матэматыка)

З пляцоўкі Вікіпедыя
Jump to navigation Jump to search

Граф (англ.: Graph) — асноўны аб'ект вывучэння матэматычнай тэорыі графаў, сукупнасць непустога мноства вяршынь і набораў пар вяршынь (сувязей паміж вяршынямі).

Аб'екты прадстаўляюцца як вяршыні, альбо вузлы графа, а сувязі — як дугі, альбо рэбры[1]. Для розных абласцей прымянення віды графаў могуць адрознівацца скіраванасцю, абмежаваннямі на колькасць сувязей і дадатковымі дадзенымі аб вяршынях альбо рэбрах.

Многія структуры, якія прадстаўляюць практычны інтарэс у матэматыцы і інфарматыцы, могуць быць прадстаўлены графамі. Напрыклад, будову Вікіпедыі можна змадэляваць пры дапамозе арыентаванага графа, у якім вяршыні — гэта артыкулы, а дугі (арыентаваныя рэбры) — гіперспасылкі (тэматычная карта).

Зноскі

  1. Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub.. pp. 19. ISBN 978-0-486-67870-2. http://store.doverpublications.com/0486678709.html. Retrieved on 8 August 2012. "A graph is an object consisting of two sets called its vertex set and its edge set."