logo

In-degree і Out-degree з дискретної математики

Щоб зрозуміти внутрішній і зовнішній ступінь вершини, ми повинні спочатку дізнатися про поняття ступеня вершини. Після цього ми можемо легко зрозуміти внутрішній і зовнішній ступінь вершини. Ми повинні знати, що внутрішню та зовнішню ступінь можна визначити лише в орієнтованому графі. Степінь вершини можна обчислити за допомогою неорієнтованого графа. У неорієнтованому графі ми не можемо обчислити внутрішній і зовнішній ступінь вершини.

Степінь вершини

Якщо ми хочемо знайти ступінь кожної вершини в графі, у цьому випадку ми повинні підрахувати кількість зв’язків, які встановлюються окремою вершиною з іншою вершиною. Іншими словами, ми можемо визначити ступінь вершини за допомогою обчислення кількості ребер, що сполучаються з цією вершиною. Степінь вершини вказується за допомогою deg(v). Якщо існує простий граф, який містить n вершин, то в цьому випадку ступінь будь-якої вершини буде:

 Deg(v) = n-1 ∀ v ∈ G 

Вершина має здатність утворювати ребро з усіма іншими вершинами в графі, окрім самої себе. Отже, у простому графі ступінь вершини буде визначено за кількістю вершин у графі мінус 1. Тут 1 використовується для самої вершини, оскільки вона сама по собі не створює циклу. Якщо граф містить вершини, які мають самопетлю, то такий тип графа не буде простим графом.

приклад:

У цьому прикладі ми маємо граф із 6 вершинами, тобто a, b, c, d, e та f. Вершина 'a' має ступінь 5, а всі інші вершини мають ступінь 1. Якщо будь-яка вершина має ступінь 1, тоді цей тип вершини буде відомий як 'кінцева вершина'.

In-degree і Out-degree з дискретної математики

Є два випадки графів, у яких ми можемо розглядати ступінь вершини, які описуються наступним чином:

  • Неорієнтований граф
  • Орієнтований граф

Тепер детально вивчимо ступінь вершини в орієнтованому графі та ступінь вершини в неорієнтованому графі.

Степінь вершини в неорієнтованому графі

Якщо існує неорієнтований граф, то в цьому типі графа не буде орієнтованого ребра. Приклади визначення ступеня вершини в неорієнтованому графі описані наступним чином:

приклад 1: У цьому прикладі ми розглянемо неорієнтований граф. Тепер ми дізнаємося ступінь кожної вершини в цьому графі.

In-degree і Out-degree з дискретної математики

рішення: У наведеному вище неорієнтованому графі всього 5 номерів вершин, тобто a, b, c, d і e. Степінь кожної вершини описується наступним чином:

  • Наведений вище граф містить 2 ребра, які зустрічаються у вершині 'a'. Отже, Deg(a) = 2
  • Цей граф містить 3 ребра, які зустрічаються у вершині 'b'. Отже, Deg(b) = 3
  • Наведений вище граф містить 1 ребро, яке зустрічається у вершині 'c'. Отже, Deg(c) = 1. Вершину c також називають висячою вершиною.
  • Наведений вище граф містить 2 ребра, які зустрічаються у вершині 'd'. Отже, Deg(d) = 2.
  • Наведений вище граф містить 0 ребер, які зустрічаються у вершині 'e'. Отже, Deg(a) = 0. Вершину e також можна назвати ізольованою вершиною.

приклад 2: У цьому прикладі ми розглянемо неорієнтований граф. Тепер ми дізнаємося ступінь кожної вершини в цьому графі.

In-degree і Out-degree з дискретної математики

рішення: У наведеному вище неорієнтованому графі є всього 5 номерів вершин, тобто a, b, c, d і e. Степінь кожної вершини описується наступним чином:

Степінь вершини a = deg(a) = 2

Степінь вершини b = deg(b) = 2

Степінь вершини c = deg(c) = 2

Степінь вершини d = deg(d) = 2

Степінь вершини e = deg(e) = 0

У цьому графі немає висячої вершини, а вершина 'e' є ізольованою вершиною.

Ступінь вершини орієнтованого графа

Якщо граф є орієнтованим графом, то в цьому графі кожна вершина повинна мати вхідний і вихідний ступінь. Припустимо, що існує орієнтований граф. У цьому графі ми можемо використати наступні кроки, щоб дізнатися ступінь уперед, відхід і ступінь вершини.

Степінь вершини

Степінь вершини можна описати як кількість ребер з v, де v використовується для позначення кінцевої вершини. Іншими словами, ми можемо описати це як кількість ребер, що приходять до вершини. За допомогою синтаксису deg-(v), ми можемо записати ступінь вершини. Якщо ми хочемо визначити ступінь вершини, для цього нам потрібно підрахувати кількість ребер, які закінчуються у вершині.

Зовнішній ступінь вершини

Вихідний ступінь вершини можна описати як кількість ребер з v, де v використовується для позначення початкової вершини. Іншими словами, ми можемо описати це як кілька ребер, що виходять з вершини. За допомогою синтаксису deg+(v), ми можемо записати вихідний ступінь вершини. Якщо ми хочемо визначити зовнішній ступінь вершини, для цього нам потрібно порахувати кількість ребер, які починаються від вершини.

Степінь вершини

Степінь вершини вказується за допомогою deg(v), що дорівнює додаванню внутрішнього ступеня вершини та зовнішнього ступеня вершини. Символічне представлення ступеня вершини описується наступним чином:

 Deg(v) = deg-(v) + deg+(v) 

приклад 1: У цьому прикладі у нас є граф, і ми повинні визначити ступінь кожної вершини.

In-degree і Out-degree з дискретної математики

рішення: Для цього ми спочатку знайдемо степінь вершини, внутрішній ступінь вершини, а потім вихідний ступінь вершини.

Як ми бачимо, наведений вище граф містить 6 вершин, тобто v1, v2, v3, v4, v5 і v6.

В ступені:

Степінь вершини v1 = deg(v1) = 1

bash else if

Степінь вершини v2 = deg(v2) = 1

Степінь вершини v3 = deg(v3) = 1

Степінь вершини v4 = deg(v4) = 5

Степінь вершини v5 = deg(v5) = 1

Степінь вершини v6 = deg(v6) = 0

Поза ступенем:

Вихідний ступінь вершини v1 = deg(v1) = 2

Вихідний ступінь вершини v2 = deg(v2) = 3

Вихідний ступінь вершини v3 = deg(v3) = 2

Вихідний ступінь вершини v4 = deg(v4) = 0

Вихідний ступінь вершини v5 = deg(v5) = 2

Вихідний ступінь вершини v6 = deg(v6) = 0

Степінь вершини

За допомогою описаного вище визначення ми знаємо, що степінь вершини Deg(v) = deg-(v) + ти+(v). Тепер розрахуємо його за допомогою такої формули:

Степінь вершини v1 = deg(v1) = 1+2 = 3

Степінь вершини v2 = deg(v2) = 1+3 = 4

Степінь вершини v3 = deg(v3) = 1+2 = 3

Степінь вершини v4 = deg(v4) = 5+0 = 5

Степінь вершини v5 = deg(v5) = 1+2 = 3

Степінь вершини v6 = deg(v6) = 0+0 = 0

приклад 2:

У цьому прикладі ми маємо орієнтований граф із 7 вершинами. Вершина 'a' містить 2 ребра, тобто 'ad' і 'ab', які виходять назовні. Отже, вершина 'a' містить вихідний ступінь, який дорівнює 2. Подібним чином, вершина 'a' також має ребро 'ga', яке йде до цієї вершини 'a'. Отже, вершина 'a' містить ступінь, який дорівнює 1.

In-degree і Out-degree з дискретної математики

рішення: Степінь вхідного та вихідного ступеня всіх вищевказаних вершин описані наступним чином:

В ступені:

Степінь вершини a = deg(a) = 1

таблиця римськими цифрами 1100

Степінь вершини b = deg(b) = 2

Степінь вершини c = deg(c) = 2

Степінь вершини d = deg(d) = 1

Степінь вершини e = deg(e) = 1

Степінь вершини f = deg(f) = 1

Степінь вершини g = deg(g) = 0

Поза ступенем:

Вихідний ступінь вершини a = deg(a) = 2

Вихідний ступінь вершини b = deg(b) = 0

Вихідний ступінь вершини c = deg(c) = 1

Вихідний ступінь вершини d = deg(d) = 1

Вихідний ступінь вершини e = deg(e) = 1

Вихідний ступінь вершини f = deg(f) = 1

Вихідний ступінь вершини g = deg(g) = 2

Степінь кожної вершини:

Ми знаємо, що степінь вершини Deg(v) = deg-(v) + ти+(v). Тепер розрахуємо його за допомогою такої формули:

Степінь вершини a = deg(a) = 1+2 = 3

java подвійний до рядка

Степінь вершини b = deg(b) = 2+0 = 2

Степінь вершини c = deg(c) = 2+1 = 3

Степінь вершини d = deg(d) = 1+1 = 2

Степінь вершини e = deg(e) = 1+1 = 2

Степінь вершини f = deg(f) = 1+1 = 2

Степінь вершини g = deg(g) = 0+2 = 2

приклад 3: У цьому прикладі ми маємо орієнтований граф із 5 вершинами. Вершина «a» містить 1 ребро, тобто «ae», які виходять назовні. Отже, вершина 'a' містить вихідний ступінь, який дорівнює 1. Аналогічно, вершина 'a' також має ребро 'ba', яке йде до цієї вершини 'a'. Отже, вершина 'a' містить ступінь, який дорівнює 1.

In-degree і Out-degree з дискретної математики

рішення: Степінь вхідного та вихідного ступеня всіх вищевказаних вершин описані наступним чином:

В ступені

Степінь вершини a = deg(a) = 1

Степінь вершини b = deg(b) = 0

Степінь вершини c = deg(c) = 2

Степінь вершини d = deg(d) = 1

Степінь вершини e = deg(e) = 1

Поза ступенем:

Вихідний ступінь вершини a = deg(a) = 1

Вихідний ступінь вершини b = deg(b) = 2

Вихідний ступінь вершини c = deg(c) = 0

Вихідний ступінь вершини d = deg(d) = 1

Вихідний ступінь вершини e = deg(e) = 1

Степінь кожної вершини:

Ми знаємо, що степінь вершини Deg(v) = deg-(v) + ти+(v). Тепер розрахуємо його за допомогою такої формули:

Степінь вершини a = deg(a) = 1+1 = 2

Степінь вершини b = deg(b) = 0+2 = 2

Степінь вершини c = deg(c) = 2+0 = 2

Степінь вершини d = deg(d) = 1+1 = 2

Степінь вершини e = deg(e) = 1+1 = 2

Приклад 4: У цьому прикладі у нас є граф, і ми повинні визначити ступінь, ступінь входу та вихід кожної вершини.

In-degree і Out-degree з дискретної математики

рішення: Для цього ми спочатку знайдемо вхідний ступінь вершини, а потім вихідний ступінь вершини.

Як ми бачимо, наведений вище граф містить 8 вершин, тобто 0, 1, 2, 3, 4, 5 і 6.

В ступені:

список java в масив

Степінь вершини 0 = deg(0) = 1

Степінь вершини 1 = deg(1) = 2

Степінь вершини 2 = deg(2) = 2

Степінь вершини 3 = deg(3) = 2

Степінь вершини 4 = deg(4) = 2

Степінь вершини 5 = deg(5) = 2

Степінь вершини 6 = deg(6) = 2

Поза ступенем:

Вихідний ступінь вершини 0 = deg(0) = 2

Вихідний ступінь вершини 1 = deg(1) = 1

Вихідний ступінь вершини 2 = deg(2) = 3

Вихідний ступінь вершини 3 = deg(3) = 2

Вихідний ступінь вершини 4 = deg(4) = 2

Вихідний ступінь вершини 5 = deg(5) = 2

Вихідний ступінь вершини 6 = deg(6) = 1

Степінь кожної вершини:

Ми знаємо, що степінь вершини Deg(v) = deg-(v) + ти+(v). Тепер розрахуємо його за допомогою такої формули:

Степінь вершини 0 = deg(0) = 1+2 = 3

Степінь вершини 1 = deg(1) = 2+1 = 3

Степінь вершини 2 = deg(2) = 2+3 = 5

Степінь вершини 3 = deg(3) = 2+2 = 4

Степінь вершини 4 = deg(4) = 2+2 = 4

Степінь вершини 5 = deg(5) = 2+2 = 4

Степінь вершини 6 = deg(5) = 2+1 = 3

Послідовність ступенів графа

Щоб визначити послідовність ступенів графа, ми повинні спочатку визначити ступінь кожної вершини в графі. Після цього запишемо ці ступені в порядку зростання. Цей порядок/послідовність можна назвати послідовністю ступенів графа.

Наприклад: У цьому прикладі ми маємо три графи з 3, 4 і 5 вершинами, а послідовність ступенів усіх графів дорівнює 3.

In-degree і Out-degree з дискретної математики

У наведеному вище графі є 3 вершини. Степінь послідовності цього графа описується так:

In-degree і Out-degree з дискретної математики

У наведеному вище графі є 4 вершини. Послідовність ступенів цього графіка описана таким чином:

In-degree і Out-degree з дискретної математики

У наведеному вище графі є 5 вершин. Послідовність ступенів цього графіка описана таким чином: