Практическая работа № Маршруты связных графов, оценка по их цене (расстоянию). Инфиксная, префиксная и постфиксная формы записи выражений


Цепь – маршрут, все ребра которого различны (кроме, возможно, концевых). Простая цепь



Download 313,65 Kb.
bet3/6
Sana04.04.2023
Hajmi313,65 Kb.
#924848
TuriПрактическая работа
1   2   3   4   5   6
Bog'liq
Практическая работа 5

Цепьмаршрут, все ребра которого различны (кроме, возможно, концевых).
Простая цепь – маршрут, все вершины которого, а, следовательно, и ребра, различны (кроме, возможно, концевых).
Цикл – замкнутая цепь, замкнутый маршрут без повторяющихся ребер.
Простой цикл – замкнутая простая цепь, p  3, p – количество вершин.
Утверждение 1.
Любой (u-v)-маршрут неориентированном графе G содержит (u-v)-простую цепь.
Утверждение 2.
Любой цикл неориентированного графа содержит в себе простой цикл.
Граф, состоящий из одного простого цикла, обозначается , граф, состоящий из одной простой цепи, обозначается , здесь – количество вершин графа.

Например:
Дан граф G. Привести примеры маршрута, цепи, простой цепи, замкнутого маршрута, цикла и простого цикла.

Маршрут M1=(1,3,4,7,2,3,4,6).
Для маршрута M1 вершины – 1,6 – концевые; 2,3,4,7 – внутренние.
Маршрут M1 – открытый маршрут, не цепь, не простая цепь (ребро (3,4) повторяется).
Маршрут M2=(1,3,4,7,2,3,4,6,1).
Маршрут M2 – замкнутый маршрут, не цикл, не простой цикл (ребро (3,4) повторяется).
Маршрут M3=(7,5,6,7,2,4).
Маршрут M3 не простая цепь (вершина 7 повторяется ).
Маршрут M4==(7,5,6,7,2,4,7).
Маршрут M4 не простой цикл (вершина 7 повторяется).
Маршрут M5=(1,3,4,7,6,2).
Маршрут M5 простая цепь.
Маршрут M6=(1,3,4,5,7,6,1).
Маршрут M6 простой цикл.


Связность в неориентированных графах
Связный неориентированный граф G – любая пара вершин соединена маршрутом (либо простой цепью) в G.
Компонента связности или компонента графа G – максимальный связный подграф графа G.
Две вершины и называются связанными в графе G, если в графе G существует маршрут между этими двумя вершинами. Вершина считается связанной сама с собой.
Связный граф состоит из одной компоненты связности.

Любой несвязный граф содержит, по крайней мере, две компоненты связности




Любой граф является объединением своих компонент связности



Либо граф, либо его дополнение связные графы




Download 313,65 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish