GRAFOVI

Што е граф?

Графовите се дискретни структури кои се состојат од темиња и ребра кои ги поврзуваат
темињата.

ребра properties

LENGTH

Ако множеството V на графот G е бесконечно графот се нарекува бесконечен граф.

POVRZANOST

Дупли ребра, повеќе од едно ребро кои поврзуваат ист пар на темиња

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

Во едноставен граф секое ребро кое сврзува две
темиња може да се претстави како {u, v}.
Нема ребра кои се претставуваат со {u, u}.

Граф кој има повеќекратни ребра се нарекува мултиграф.

{u, v} се нарекува ребро со кратност m.

сите ребра ги гледаме како различни копии на {u, v}

Немат алки и дупли ребра - псевдограф

Ако множеството V на графот G е конечно грaфот се нарекува конечен граф.

Алка (, јамка, лупа) – ребро кое поврзува исто теме ({u, u}).**

ORIENTACIJA

Неориентирани ребра – оперираат во двата правци.

Ако графот се состои само од неориентирани ребра се нарекува неориентиран граф.

Ориентирани ребра - оперираат само во еден правец.

Графови со ориентирани ребра се нарекуваат ориентирани графови.

ориентирани ребра + неориентирани ребра = мешан граф.

темиња properties

Степен на теме.

Неориентиран

Ориентиран

Типови на едноставни графови

Комплетен граф со n темиња, Kn

Циклус со n темиња, Cn

Тркало со n темиња, Wn

Соседни темиња

n - Коцка со n темиња, Qn

Бипартитни (дводелни) графови

  1. Може да се обои со 2 бои.
  1. Нема циклуси кои се од непарна должина, т.е (3)

Подграф

Унија

Репрезентирање на графови

листи на соседство

матрици на соседство

други properties

Изоморфизам

Пат во граф

Циклус

Пат во ориентиран граф

Сврзаност во неориентиран граф

Сврзани компоненти

Засек

Броење на патишта меѓу темиња

Еден граф G = (V, E) се состои од множество V, непразно множество од темиња (или
јазли) и множество Е, множество од ребра.

други properties ADVANCED

Ојлерово движење(циклус)

Ојлеров пат

Сите V, V>=2 имаат парен степен.

V>=2 && две V имаат непарен степен != циклус

Пат кој поминува точно по еднаш по секое ребро и се
враќа на почетното теме.

Едноставен пат кој ги содржи сите ребра од графот

Хамилтонов пат

Едноставен пат кој поминува точно по еднаш по секое теме.

Хамилтонов циклус

Едноставен циклус кој поминува точно по еднаш по секое теме.

Теорема на Дирац

Теорема на Оре

Ојлер = Сврзан

Хамилтон = Едноставен

Тежински граф

Најкус пат

Алгоритамот на Дикстра

Планарни (рамнински) графови

Ако може да се нацрта во рамнина без вкрстување на ребрата.

Региони (области)

Формула на Ојлер

r = e - v + 2.

сврзан планарен прост граф

  1. П1 - ако v ≥3, тогаш e ≤ 3v - 6.
  2. П2 - G има теме со степен кој не надминува 5.
  3. П3 - ако v≥ 3 и нема циклуси со должина 3, тогаш e ≤2v - 4.

Теорема на Куратовски

Хомеомофни графови

Боење на графови

2Д карта - 4 бои

Хроматски број (најмал број за да се обои), на планарен не е поголем од 4.

Дуални графови

bijection that preserves adjacency

vi, vi+1 za site i = {1, 2, ... n-1} + v1, vn