2 3_Діскретная математика 3

Визначимо властивості відносини.

1) рефлексивно. тому . У графі рефлексивність відображена наявністю петлі в кожній вершині.

2) Чи не антирефлексивне. тому наявність рефлексивності - заперечує антирефлексивне.

3) Чи не симетрично. тому при наявності пари (1, 2) відсутня пара (2, 1), значить порушується правило: (в графі відсутні симетричні ребра).

4) Чи не антисиметрично. тому воно рефлексивно, значить, правило порушується пріx = y.

6) транзитивності. тому якщо «x дільник y» і «y дільник z», то «x дільник z». У графі всі ланцюжки побудовані з x в y - замикаються ребром (x, y).

Наприклад: (1, 3), (3, 6) (1, 6)

(1, 2), (2, 2) (1, 2) і т.д.

7) Чи не повне. тому нема про будь-якій парі x і y можна сказати або. Наприклад: (2, 5) R і (5, 2) R. Такі вершини не пов'язані ребрами.

Таким чином, ставлення рефлексивно, тотожне, транзитивно. значить є відношенням порядку.

2) Для побудованого графа знайти:

д) радіус, діаметр, центр, периферійні вершини;

Центром графа називається вершина, в якій досягається найменша з відхиленнями. Центрів може бути декілька, тому що Відхилення тільки у вершини 1, отже вона - центр.

Радіусом графа називається відхилення його центра p (G) = d (1) = 1.

Діаметром неориентированного графа називається максимальна відстань між вершинами. А відстань - це довжина найменшої елементарної ланцюга. Діаметром фграфа можна назвати

2) довжину максимального елементарного шляху, тоді Д (G) = 1.

Периферійної вершиною називається вершина з найбільшими відхиленнями. Це 2, 3, 4, 5, 6.

е) число внутрішньої і зовнішньої стабільності.

Внутрішнє стійке безліч графа G (x) - це таке підмножина S безлічі вершин X. будь-які дві вершини якого не суміжні. Число внутрішньої стійкості α (G) - потужність максимального внутрішньо-стійкого безлічі.

, ,

Зовні стійке безліч графа G (x) - це таке підмножина T безлічі вершин X. що будь-яка вершина з Х \ Т = з'єднана дугою з вершиною з Т.

Число зовнішньої стійкості β (G) - потужність мінімального зовнішньо-стійкого безлічі. ,

3) Для двох довільно вибраних графів знайти декартовій твір і декартову суму.

а) безліч вершин X є декартових твором множин X1 і X2. тобто X1 × X2 =.

б) безліч вершин, суміжних з вершиною (x1, x2) декартова твори двох графів визначається як декартовій твір множин вершин графа G1 (X1), суміжних x1 і графа G2 (X2) суміжних з x2.

1) Визначимо безліч вершин графа G (X) і побудуємо граф:

Вершини суміжні з a.

Вершини суміжні з x. , ТогдаG (a, x) =.