Незалежні множини
Наприклад:наступні графи ізоморфні один одному.
Граф
Наприклад:граф
Наприклад:граф
Незалежні множини
Незалежне безліч вершин– підмножина вершин графаG:SVтаке, що будь-які дві вершини в ньому несумежні, тобто жодна пара вершин не з'єднана руба.
підграф, породжений незалежною множиною–порожній граф.
Максимальна незалежна множина –не є власним підмножиною іншої незалежної множини.
Найбільше незалежне безліч –найбільше за потужністю серед усіх незалежних множин.
Кількість незалежності(G) графаG–потужність найбільшої незалежної множини.
Максимальні незалежні множини
Найбільша незалежна множина графаG:.
Кліка –підмножина вершин графаGтаке, що будь-яка пара з цієї множини є суміжною.
підграф, породжений клікою – повний граф.
Максимальна кліка –не є власним підмножиною жодної іншої кліки графаG.
Найбільша кліка –найбільша за потужністю серед усіх інших клік графаG.
Клікове число або щільність(G) графаG–потужність найбільшої кліки.
S1=;