Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

 

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

Визначення. Маршрутом в G називається скінченна або нескінченна послідовність ребер S = {…, e0, e1, …, en, …} в якій кожні два сусідні ребра ei - 1 і ei мають спільну вершину, тобто

e0 = (v0, v1)

e1 = (v1, v2)

e2 = (v2, v3)

. . .

en = (vn, vn + 1).

 

Визначення. Якщо в S немає ребер, які стоять перед e0, то v0 називається початковою вершиною S; якщо немає ребер після en - 1, то vn - кінцевою вершиною. Якщо вершина vi належить і ei - 1 і ei, то вона називається внутрішньою.

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

S = S(v0, vn)

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

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

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

S(vi, vj) = (ei, …, ei + 1, …, ej - 1)

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

На рис.5 маршрут S = (e1, e2, e3, e4, e5) є скінченним, має довжину 5, початкову вершину v1 і кінцеву v5. Маршрут S = (e2, e3, e4) є підмаршрутом даного маршруту.

 

Рис.5

 

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

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

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

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

 


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

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




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

<== попередня сторінка | наступна сторінка ==>
Частини, суграфи і підграфи графу. | Зв’язаність

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.