Граф (математика)

A drawing of a labeled graph on 6 vertices and 7 edges.

Граф - Граф (грекше-жазамын) – төбелер деп аталатын шектеулі нүктелерддің жиынтығы;төберлердің кейбіреулері графтың қырлары деп аталатын сызықтарымен байланысқан болады. Төбелердің жиыны (v) және реттелмеген және реттелген төбелердің (қырлар мен доғалар) жиынтығы (e) граф болып табылады: Граф “G” (V,E) болып белгілінеді. Тек қырлары ғана қамтитын граф – бағдарланбаған, ал тек доғаларды қамтитыны бағдарланған граф деп аталады. Кез – келген екі төбені қосатын тізбегі болатын граф – байланысқан граф болып табылады.

Граф — нысандар мен олардың арасындағы байланыстар жиынтығын айтады. Нысандар графтың төбелері деп, ал байланыстар граф қабырғалары деп аталады. Графты қолданылатын саласына байланысты байланыстар саны, қабырғалар бағытымен және төбелеріндегі әртекті қасиеттерімен ажыратады. Көптеген есептерді, нысандарды графтармен сипаттауға болады. Мысалға Уикипедияны да графпен сипаттауға болады — төбелері мақалалар, ал қабырғалары — гиперсілтемелер.

Граф

Граф, немесе бағытталмаған граф $G$ — бұл $G:=(V,E)$ келесі шарттарды қанағаттандыратын ретті жұптар жиынтығы:

• $V$ — төбелер немесе түйіндер бос емес жиыны ;
• $E$ — қабырғалар деп аталатын төбелерден құралған жұптар (бағытталмаған графта — ретсіз).

Төбелері мен қабырғаларын кейде граф элементтері деп те атайды, граф төбелер санын $|V|$ — граф дәрежесі, қабырғалар санын $|E|$ — граф өлшемі деп атайды.

$u$ және $v$ төбелері $e=\{u,v\}$ қабырғасының шеткі төбелері (немесе шеттері) деп аталады. Бір қабырғаның екі шеткі төбелері көршілес деп атады.

Ортақ шеткі төбелері бар екі қабырға түйіндес деп аталды.

Шеткі төбелер жиыны бірдей болатын екі қабырға еселі деп аталады.

Шеткі төбелер беттесетін қабырғаны ілмек аталыды, яғни $e=\{v,v\}$ болса.

$V$ төбесінің дәрежесі $\deg V$ деп оған тірелетін қабырғалар санын айтады (ілмекті екі рет санайды).

Төбе ешқандай қабырғаның шеті болмаса оңашаланған болады; ал егер тек қана бір қабырға шеті болса салбыраулы (немесе жапырақ) болады.

Тағы қараңыз

• Графтар теориясы

Сілттемелер

• Balakrishnan V. K. Graph Theory — 1st. — McGraw-Hill. — ISBN 0-07-005489-4.
• Berge Claude Théorie des graphes et ses applications — Dunod, Paris: Collection Universitaire de Mathématiques, II, 1958. — P. viii+277. Translation:  — Dover, New York: Wiley, 2001.
• Biggs Norman Algebraic Graph Theory — 2nd. — Cambridge University Press, 1993. — ISBN 0-521-45897-8.
• Bollobás Béla Modern Graph Theory — 1st. — Springer. — ISBN 0-387-98488-7.
• Bang-Jensen J. Digraphs: Theory, Algorithms and Applications — Springer, 2000.
• Graph Theory — 3rd. — Berlin, New York: Springer-Verlag, 2005. — ISBN 978-3-540-26183-4..
• Handbook of Combinatorics / Graham, R.L., Grötschel, M., and Lovász, L — MIT Press, 1995. — ISBN 0-262-07169-X.
• Gross Jonathan L. Graph Theory and Its Applications — CRC Press. — ISBN 0-8493-3982-0.
• Handbook of Graph Theory / Gross, Jonathan L., & Yellen, Jay — CRC. — ISBN 1-58488-090-2.
• Harary Frank Graph Theory — Addison Wesley Publishing Company. — ISBN 0-201-41033-8.
• Iyanaga Shôkichi Encyclopedic Dictionary of Mathematics — MIT Press, 1977. — ISBN 0-262-09016-3.
• Zwillinger Daniel CRC Standard Mathematical Tables and Formulae — 31st. — Chapman & Hall/CRC. — ISBN 1-58488-291-3.

Арғы оқылымдар

• Trudeau Richard J. Introduction to Graph Theory — Corrected, enlarged republication.. — New York: Dover Publications, 1993. — ISBN 978-0-486-67870-2.

Сыртқы сілттемелер

• A searchable database of small connected graphs
• VisualComplexity.com Мұрағатталған 19 шілденің 2008 жылы. — A visual exploration on mapping complex networks
• Weisstein, Eric W. Graph (ағыл.) на сайте Wolfram MathWorld.
• Intelligent Graph Visualizer — IGV create and edit graph, automatically places graph, search shortest path (+coloring vertices), center, degree, eccentricity, etc.
• Visual Graph Editor 2 — VGE2 designed for quick and easy creation, editing and saving of graphs and analysis of problems connected with graphs.
• GraphsJ Мұрағатталған 10 наурыздың 2013 жылы. — GraphsJ is an open source didactic Java software which features an easy-to-use GUI and interactively solves step-by-step many graph problems. Extensible via its Java SDK.
• GraphClasses — Information System on Graph Classes and their Inclusions.
• Graph Theory Software Мұрағатталған 13 наурыздың 2013 жылы.

Дереккөздер

Математика әлемі