Граф

Граф — апстрактен математички објект. Цртежот кој се состои од јазли и гранки е само геометриски приказ на графот. Сепак, вообичаено е таквата слика да се нарекува граф. Бидејќи графот е составен од јазли и гранки кои поврзуваат по два јазли, тогаш од таму е можно да се изведе формалната дефиниција на графот.

Оваа општа дефиниција ни овозможува да го примениме графот не само во математиката, туку и во информатиката, електротехниката и инженерството воопшто, како и во хемијата, лингвистиката, економијата и многу други области.

 Дефиниции 
Како што беше претходно споменато, при дефинирањето на поимот граф, користиме термини од теоријата на множества. Така една строга дефиниција гласи

Додека друга дозволува бесконечен број јазли (и гранки) Дискретне математичке структуре, Драгош Цветковић

Поимот граф може да се генерализира ако прифатиме дека е можно да има повеќе од една гранка со иста ориентација, односно да има повеќе јамки. Таквиот граф тогаш се нарекува мултиграф. Обичен граф тогаш е посебен случај на мултиграф.

Дефиницијата за таков мултиграф би била:

Во секој случај, графот е зададен ако се зададени две множества, множество јазли и множество гранки.

 Видови графови 
Граф кој има конечен број на јазли се нарекува конечен граф. Аналогно на тоа, графот со бесконечен број јазли се нарекува бесконечен граф.

Ако не е важно дали гранката на графот AB е иста со BA и тоа важи за сите гранки на графот, тогаш ρ е симетрична релација, а графот е симетричен или неориентиран . Во таквите графови, стрелките на цртежот се изоставуваат.

Ако сите гранки на графот имаат стрелки, односно се ориентирани, тогаш целиот граф е ориентиран или антисиметричен.

Поврзан граф е таков неориентиран граф каде што може со пат да се поврзат кои било два јазли. Ако има два јазли кои не можат да се поврзат, графот не е поврзан.

 Поими 
Гранка на граф што започнува од еден јазол и завршува во истиот тој јазол се нарекува јамка.

Неповрзан граф се состои од најмалку два неповрзани дела. Таквите делови се нарекуваат компоненти на поврзаност на графот.

Ако, со отстранување на еден јазол од графот, тој се распадне, односно се зголемува бројот на компоненти на поврзаност, тогаш тој јазол е артикулационен јазол.

Ако со отстранување на една гранка графот се распаѓа, гранката се нарекува мост на графот.

Степен на јазол на граф е бројот на гранки на графот што имаат крај во јазолот. Ако гранка поврзува јазол со себе, тогаш таа се брои двапати.

Гранката што го поврзува јазолот со степен еден е висечка гранка.

 Поврзано 

 Теорија на графови
 Хиперграф
 Планарен граф

 Наводи 

 Надворешни врски 

Категорија:Графови
Категорија:Математички теории
Категорија:Зборови што ги нема во ТРМЈ