|
Guruh talabasi rejabov nodirbek adiljonovichning
|
| bet | 3/6 | | Sana | 30.09.2023 | | Hajmi | 107.7 Kb. | | #85737 |
Bog'liq Diskret tuzilmalar 1. KTE xxx, diskerit bazza 22.02.2023, Тестлар Big Data-uz, MUSTAQIL TA'LIM MAVZULARI, 713, 1-dedlayn G, 1-6 simsiz1- misol. 1- shaklda tasvirlangan grafni qaraymiz. Avvalo bu grafning Eyler grafi bo'lishi shartini, ya’ni 1- teorema shartlarining bajarilishini tekshiramiz.
nV = 4
nV = 4
INF = 999
def floyd_warshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:
print(distance[i][j], end=" ")
print(" ")
G = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
floyd_warshall(G)
Marshrutlar va zanjirlar haqida umumiy ma’lumotlar. Uchlari to‘plami V = {v1;v2,...,vm} va qirralar korteji U — {u1,u2,...,un} bo’lgan oriyentirlanmagan G = (V,U) graf berilgan bo‘lsin. Bu G grafdagi uchlar va qirralaming har ikki qo‘shni qirralari umumiy chetki uchga ega
(…,vi,ui,vi2,ui2,vi3,..)
ko'rinishidagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. Marshrutni uning uchlari ketma-ketligi (...,vj1,vj2,...) yoki qirralari ketma-ketligi (…,uj1,uj2,...) ko‘rinishida ham belgilash mumkin .Agar marshrutda qandaydir uchdan oldin uchlar bo‘lmasa, bu uchni marshrutning boshlang‘ich uchi deb, shu uchdan keyin marshrutga tegishli uchlar bo‘lmaganda esa, uni marshrutning oxirgi uchi deb ataydilar. Agar marshrutning boshlang‘ich uchi vp va oxirgi uchi vq bo‘lsa, u holda uni vp uchdan vq uchga yo‘nalgan marshrut yoki chetlari vp va vq bo‘lgan marshrut deb ataladi.
Marshrutdagi ikkita qoshni qirralarga tegishli uch ichki uch yoki oraliq uch deb ataladi.
Marshrutda qirralar va uchlar takrorlanishi mumkin boMgani uchun marshrutning ichki uchi, bir vaqtning o ‘zida, uning boshlang‘ich va (yoki) oxirgi uchi bo‘lishi ham mumkin va teskarisi, marshrutning boshlang‘ich va (yoki) oxirgi uchi uning ichki uchi bo‘lishi ham mumkin.
Tabiiyki,marshrut:
- boshlang‘ich uchga ham oxirgi uchga ham ega bo‘lmasligi mumkin (bunday marshrut ikki tomonlama cheksiz marshrut deb ataladi);
boshlangich uchga ega bo‘lib, oxirgi uchga ega bo‘lmasligi mumkin yoki, aksincha, oxirgi uchga ega bo'lib, boshlangich uchga ega bo‘lmasligi mumkin (bir tomonlama cheksiz marshrut);
- yagona qirradan iborat bo‘lishi mumkin (notrivial marshrut);
birorta ham qirraga ega bo‘lmasligi mumkin (nol marshrut yoki trivial marshrut).
|
| |
