• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Деякі визначення

Маршрути, ланцюги і цикли

Нехай G - неорієнтований граф.

Визначення. Маршрутом в G називається скінченна або нескінченна послідовність ребер S = {…, e₀, e₁, …, e_n, …} в якій кожні два сусідні ребра e_{i - 1} і e_i мають спільну вершину, тобто

e₀ = (v₀, v₁)

e₁ = (v₁, v₂)

e₂ = (v₂, v₃)

. . .

e_n = (v_n, v_{n + 1}).

Визначення. Якщо в S немає ребер, які стоять перед e₀, то v₀ називається початковою вершиною S; якщо немає ребер після e_{n - 1}, то v_n - кінцевою вершиною. Якщо вершина v_i належить і e_{i - 1} і e_i, то вона називається внутрішньою.

Визначення. Якщо маршрут S має початкову і кінцеву вершини, то він називається скінченним; якщо S має початок і не має кінцевої вершини (або навпаки), то він називається односторонньо-нескінченним; якщо немає ні початкової вершини ні кінцевої – то двосторонньо-нескінченними. Якщо S має початкову вершину v₀ і кінцеву v_n, то позначається

S = S(v₀, v_n)

(тобто S - це маршрут довжини n, який з’єднує вершини v₀ і v_n ).

Визначення. Якщо v₀ = v_n, то маршрут називається циклічним.

Визначення. Якщо v_i і v_j - дві вершини маршруту S, то

S(v_i, v_j) = (e_i, …, e_{i + 1}, …, e_{j - 1})

називається підмаршрутом.

На рис.5 маршрут S = (e₁, e₂, e₃, e₄, e₅) є скінченним, має довжину 5, початкову вершину v₁ і кінцеву v₅. Маршрут S = (e₂, e₃, e₄) є підмаршрутом даного маршруту.

Рис.5

Визначення. Ланцюг – це маршрут, кожне ребро якого зустрічається рівно один раз. Циклічний ланцюг називається циклом.

Визначення. Нециклічний ланцюг називається простим, якщо в ньому жодна вершина не повторюється. Цикл з початком (і кінцем) в v₀ називається простим, якщо в ньому жодна вершина, крім v₀ не повторюється.

Зрозуміло, що частина ланцюга або циклу теж є ланцюгом або циклом.

Для орієнтованих графів вводяться в розгляд як неорієнтовані маршрути (ланцюги) (тобто не приймається до уваги орієнтація ребер), так і орієнтовані маршрути (ланцюги).

Читайте також:

1. I визначення впливу окремих факторів
2. II. Визначення мети запровадження конкретної ВЕЗ з ураху­ванням її виду.
3. II. Мотивація навчальної діяльності. Визначення теми і мети уроку
4. Ocнoвнi визначення здоров'я
5. Агітація за і проти та деякі особливості її техніки.
6. Алгебраїчний спосіб визначення точки беззбитковості
7. Аналіз службового призначення деталей та конструктивних елементів обладнання харчових виробництві, визначення технічних вимог і норм точності при їх виготовленні
8. Аналіз стратегічних альтернатив та визначення оптимальної стратегії формування фінансових ресурсів
9. Аналіз ступеня вільності механізму. Наведемо визначення механізму, враховуючи нові поняття.
10. Балансова теорія визначення статі. Диференціація статі і роль гормонів у цьому процесі.
11. Безстатеве розмноження, його визначення та загальна характеристика. Спори — клітини безстатевого розмноження, способи утворення і типи спор.
12. Біостратиграфічні методи визначення віку порід

Переглядів: 738