АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Основні терміни

Лекція 13

Неорієнтовані графи і термінологія

Геометричний граф - це сукупність точок X і простих кривих У, кінці яких є точки з X, а самі криві попарно не мають спільних внутрішніх точок. Точки з X називаються вершинами, криві з У — ребрами графа.

X = {x₁, x₂, x_з,x₄}

Y = {у₁, у₂, у₃, у₄, у₅, у₆, у₇}.

Позначення для графа: С = (X, Y).

Основні терміни

Суміжні вершини (х₂, х₃) — це вершини, з'єднані ребром, су­міжні ребра (у₂, у_з) — це ребра, що мають спільну вершину х₂.

Вершина х₂ і ребро у₃ інциденті одна одному, якщо точка х₂ є кінець кривої у_3.

Петля (у₄) — замкнене ребро.

Ізольова­на вершина (х₄) неінцидентна жодному ребру.

Паралельні (кратні) ребра (у_1, у₂, у₅) — це ребра, що ін­циденті одній парі вершин (х₁, х₂).

Маршрут, з'єднуючий вершини х_k і x_n — скінченна пос­лідовність ребер та інцидентних їм вершин, що складають неперервну криву з кінцями х_k і x_n. Число ребер у маршруті називається його довжиною (включаючи внесок повторюваних ребер).

Маршрут замкнений, якщо кінці його співпадають (х_k = х_n).

Маршрут називається ланцюгом, якщо всі його ребра різ­ні, і простим ланцюгом, якщо всі його вершини (крім, може, кінців ланцюга) різні.

Цикл — це замкнений ланцюг (простий цикл, якщо лан­цюг простий).

Граф називається зв'язним, якщо будь-яка пара його вер­шин з'єднується ланцюгом.

Підграф — будь-яка частина графа, що сама є графом.

Компонента (зв'язності) — максимальний зв'язний під­граф у графі

Граф C = (X, У) називається:

— порожнім, якщо множина його ребер порожня;

— простим, якщо він не містить петель і паралельних ребер;

— повним, якщо він простий і кожна пара вершин суміжна;

— регулярним або однорідним (степені n), якщо степені всіх його вершин однакові;

— деревом, якщо він не містить циклів і зв'язний;

— мультиграфом, якщо він містить паралельні ребра;

— псевдографом, якщо він містить петлі та кратні ребра.

Точка зчеплення графа — вершина, видалення якої разом з інцидентними їй ребрами призводить до збільшення числа компонент графа.

Відстань між вершинами графа — довжина найкоротшого ланцюга між ними.

Діаметром графа називається максимальна відстань у графі.

Дата добавления: 2015-09-27 | Просмотры: 370 | Нарушение авторских прав