Граф
Граф — апстрактен математички објект. Цртежот кој се состои од јазли и гранки е само геометриски приказ на графот. Сепак, вообичаено е таквата слика да се нарекува граф. Бидејќи графот е составен од јазли и гранки кои поврзуваат по два јазли, тогаш од таму е можно да се изведе формалната дефиниција на графот.
Оваа општа дефиниција ни овозможува да го примениме графот не само во математиката, туку и во информатиката, електротехниката и инженерството воопшто, како и во хемијата, лингвистиката, економијата и многу други области.
Дефиниции
уредиКако што беше претходно споменато, при дефинирањето на поимот граф, користиме термини од теоријата на множества. Така една строга дефиниција гласи
Граф е подреден пар G = (X, ρ), каде X е конечно непразно множество, а ρ бинарна релација во Х.
Додека друга дозволува бесконечен број јазли (и гранки) [1]
Нека X е непразно множество и ρ бинарна релација во Х. Подредениот пар G = (X, ρ) се нарекува граф. Елементите од множеството Х се јазли на графот, а елементите на множеството ρ гранки на графот.
Поимот граф може да се генерализира ако прифатиме дека е можно да има повеќе од една гранка со иста ориентација, односно да има повеќе јамки. Таквиот граф тогаш се нарекува мултиграф. Обичен граф тогаш е посебен случај на мултиграф.
Дефиницијата за таков мултиграф би била:
Нека X е непразно множество и U една комбинација со повторување од множеството Х2. Подредениот пар G = (X, U) се нарекува мултиграф.
Во секој случај, графот е зададен ако се зададени две множества, множество јазли и множество гранки.
Видови графови
уредиГраф кој има конечен број на јазли се нарекува конечен граф. Аналогно на тоа, графот со бесконечен број јазли се нарекува бесконечен граф.
Ако не е важно дали гранката на графот AB е иста со BA и тоа важи за сите гранки на графот, тогаш ρ е симетрична релација, а графот е симетричен или неориентиран . Во таквите графови, стрелките на цртежот се изоставуваат.
Ако сите гранки на графот имаат стрелки, односно се ориентирани, тогаш целиот граф е ориентиран или антисиметричен.
Поврзан граф е таков неориентиран граф каде што може со пат да се поврзат кои било два јазли. Ако има два јазли кои не можат да се поврзат, графот не е поврзан.
Поими
уредиГранка на граф што започнува од еден јазол и завршува во истиот тој јазол се нарекува јамка.
Неповрзан граф се состои од најмалку два неповрзани дела. Таквите делови се нарекуваат компоненти на поврзаност на графот.
Ако, со отстранување на еден јазол од графот, тој се распадне, односно се зголемува бројот на компоненти на поврзаност, тогаш тој јазол е артикулационен јазол.
Ако со отстранување на една гранка графот се распаѓа, гранката се нарекува мост на графот.
Степен на јазол на граф е бројот на гранки на графот што имаат крај во јазолот. Ако гранка поврзува јазол со себе, тогаш таа се брои двапати.
Гранката што го поврзува јазолот со степен еден е висечка гранка.
Поврзано
уредиНаводи
уреди- ↑ Дискретне математичке структуре, Драгош Цветковић
