- •23 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
- •24 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
- •25 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
- •26 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
- •27 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
- •28 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
- •29 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
- •30 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
1 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 1), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,3} С2 = {2,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,5} С4 = {4,6,7}
С5 = {1,2,3,5,6} С5 = {4,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=2+2+3+2+3+3=15
2 Компанія кабельного телебачення (пункт 2) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {2} С1 = {1,3,4,5,6,7}
С2 = {2,3} С2 = {1,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,5} С4 = {4,6,7}
С5 = {1,2,3,5,6} С5 = {4,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=2+2+3+2+3+3=15
3 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт ), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,2} С2 = {3,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,5} С4 = {4,6,7}
С5 = {1,2,3,5,6} С5 = {4,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=2+2+3+3+3+3=16
4 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт ), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {2} С1 = {1,3,4,5,6,7}
С2 = {2,3} С2 = {1,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,5} С4 = {4,6,7}
С5 = {1,2,3,5,6} С5 = {4,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=2+3+3+3+3+3=17
5 Компанія кабельного телебачення (пункт 3) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {3} С1 = {1,2,4,5,6,7}
С2 = {3,7} С2 = {1,2,4,5,6}
С3 = {1,3,7} С3 = {2,4,5,6}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,5,7} С5 = {4,6}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=2+3+3+3+3+4=18
6 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт ), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,2} С2 = {3,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,5,7} С5 = {4,6}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+2+3+3+3+4=18
7 Компанія кабельного телебачення (пункт 1) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,2} С2 = {3,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,5} С4 = {4,6,7}
С5 = {1,2,3,4,5} С5 = {6,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+3+3+4+4=20
8 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 5), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {5} С1 = {1,2,3,4,6,7}
С2 = {4,5} С2 = {1,2,3,6,7}
С3 = {3,4,5} С3 = {1,2,6,7}
С4 = {1,3,4,5} С4 = {2,6,7}
С5 = {1,2,3,4,5} С5 = {6,7}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+3+3+3+4=19
9 Компанія кабельного телебачення (пункт 5) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {5} С1 = {1,2,3,4,6,7}
С2 = {4,5} С2 = {1,2,3,6,7}
С3 = {3,4,5} С3 = {1,2,6,7}
С4 = {3,4,5,7} С4 = {1,2,6}
С5 = {1,3,4,5,7} С5 = {2,6}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+4+3+3+4=20
10 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 7), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {7} С1 = {1,2,3,4,5,6}
С2 = {1,7} С2 = {2,3,4,5,6}
С3 = {1,2,7} С3 = {3,4,5,6}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,6,7} С5 = {4,5}
С6 = {1,2,3,4,6,7} С6 = {5}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+4+3+4+3=20
11 Компанія кабельного телебачення (пункт ) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,7} С2 = {2,3,4,5,6}
С3 = {1,2,7} С3 = {3,4,5,6}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,4,7} С5 = {5,6}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+4+4+4+3+4=22
12 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 7), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {7} С1 = {1,2,3,4,5,6}
С2 = {1,7} С2 = {2,3,4,5,6}
С3 = {1,2,7} С3 = {3,4,5,6}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,6,7} С5 = {4,5}
С6 = {1,2,3,4,6,7} С6 = {5}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+4+3+4+4+3=21
13 Компанія кабельного телебачення (пункт 1) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,7} С2 = {2,3,4,5,6}
С3 = {1,2,7} С3 = {3,4,5,6}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,4,7} С5 = {5,6}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+3+4+3+3=19
14 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 3), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {3} С1 = {1,2,4,5,6,7}
С2 = {2,3} С2 = {1,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,4,7} С5 = {5,6}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+3+3+4+3=19
15 Компанія кабельного телебачення (пункт 6) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {5} С1 = {1,2,3,4,6,7}
С2 = {4,5} С2 = {1,2,3,6,7}
С3 = {3,4,5} С3 = {1,2,6,7}
С4 = {2,3,4,5} С4 = {1,6,7}
С5 = {1,2,3,4,5} С5 = {6,7}
С6 = {1,2,3,4,5,7} С6 = {6}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=4+3+3+3+4+4=21
16 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 4), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {4} С1 = {1,2,3,5,6,7}
С2 = {3,4} С2 = {1,2,5,6,7}
С3 = {2,3,4} С3 = {1,5,6,7}
С4 = {2,3,4,6} С4 = {1,5,7}
С5 = {1,2,3,4,6} С5 = {5,7}
С6 = {1,2,3,4,6,7} С6 = {5}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+2+3+4+4=19
17 Компанія кабельного телебачення (пункт ) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {2} С1 = {1,3,4,5,6,7}
С2 = {2,6} С2 = {1,3,4,5,7}
С3 = {1,2,6} С3 = {3,4,5,7}
С4 = {1,2,3,6} С4 = {4,5,7}
С5 = {1,2,3,4,6} С5 = {5,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=2+3+3+3+4+4=19
18 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 1), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,3} С2 = {2,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,6} С4 = {4,5,7}
С5 = {1,2,3,4,6} С5 = {5,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+2+3+4+4=19
19 Компанія кабельного телебачення (пункт ) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,2} С2 = {3,4,5,6,7}
С3 = {1,2,6} С3 = {3,4,5,7}
С4 = {1,2,3,6} С4 = {4,5,7}
С5 = {1,2,3,6,7} С5 = {4,5}
С6 = {1,2,3,4,6,7} С6 = {5}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+2+3+3+3+4=18
20 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт 7), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {7} С1 = {1,2,3,4,5,6}
С2 = {1,7} С2 = {2,3,4,5,6}
С3 = {1,2,7} С3 = {3,4,5,6}
С4 = {1,2,6,7} С4 = {3,4,5}
С5 = {1,2,3,6,7} С5 = {4,5}
С6 = {1,2,3,4,6,7} С6 = {5}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+2+3+3+3=17
21 Компанія кабельного телебачення (пункт ) планує прокласти кабельну мережу до нових мікрорайонів, відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,7} С2 = {2,3,4,5,6}
С3 = {1,2,7} С3 = {3,4,5,6}
С4 = {1,2,3,7} С4 = {4,5,6}
С5 = {1,2,3,4,7} С5 = {5,6}
С6 = {1,2,3,4,6,7} С6 = {5}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+4+3+3+4+3=20
22 Телефонна компанія планує підключити нові мікрорайони до телефонної станції (пункт ), відстань між мікрорайонами вказані на схемі. Необхідно спроектувати найбільш економічну кабельну мережу. Проект мережи показати на схемі подвійною лінією.
С0 = 0 С0 = {1,2,3,4,5,6,7}
С1 = {1} С1 = {2,3,4,5,6,7}
С2 = {1,3} С2 = {2,4,5,6,7}
С3 = {1,2,3} С3 = {4,5,6,7}
С4 = {1,2,3,4} С4 = {5,6,7}
С5 = {1,2,3,4,6} С5 = {5,7}
С6 = {1,2,3,4,5,6} С6 = {7}
С7 = {1,2,3,4,5,6,7} С7 = 0
Lmin=3+3+3+4+3+4=20
23 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
№ узла |
Метка |
Статус метки |
1 |
[0,-] |
Постоянная (П) |
2 |
[4,1] |
Временная (В)→П |
3 |
[3,1] |
В→П |
7 |
[2,1] |
В→П |
4 |
[6,3] |
В→П |
7--- |
[7,3] |
В |
7--- |
[9,4] |
В |
5 |
[6,2] |
В→П |
5--- |
[7,3] |
В |
5--- |
[9,4] |
В |
2--- |
[5,3] |
В |
6 |
[8,5] |
В→П |
2--- |
[12,6] |
В |
24 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
№ узла |
Метка |
Статус метки |
1 |
[0,-] |
Постоянная (П) |
2 |
[4,1] |
Временная (В)→П |
3 |
[4,1] |
В→П |
7 |
[3,1] |
В→П |
4 |
[7,3] |
В→П |
7--- |
[8,3] |
В |
7--- |
[10,4] |
В |
5 |
[7,2] |
В→П |
5--- |
[8,3] |
В |
5--- |
[10,4] |
В |
6 |
[9,5] |
В→П |
2--- |
[13,6] |
В |
2--- |
[6,3] |
В |
25 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
№ узла |
Метка |
Статус метки |
1 |
[0,-] |
Постоянная (П) |
2 |
[5,1] |
Временная (В)→П |
3 |
[4,1] |
В→П |
7 |
[6,1] |
В→П |
4 |
[7,3] |
В→П |
7--- |
[8,3] |
В |
7--- |
[9,4] |
В |
5 |
[8,3] |
В→П |
5--- |
[8,2] |
В |
5--- |
[10,4] |
В |
6 |
[11,5] |
В→П |
2--- |
[13,6] |
В |
2--- |
[7,3] |
В |
26 Знайти найкоротшу відстань від пункта 1 до усіх інших пунктів мережі. Відстань показана біля кожного ребра мережі.
№ узла |
Метка |
Статус метки |
1 |
[0,-] |
Постоянная (П) |
2 |
[5,1] |
Временная (В)→П |
3 |
[5,1] |
В→П |
7 |
[6,1] |
В→П |
4 |
[8,3] |
В→П |
7--- |
[6,3] |
В |
7--- |
[10,4] |
В |
5 |
[7,2] |
В→П |
5--- |
[9,3] |
В |
5--- |
[11,4] |
В |
6 |
[10,5] |
В→П |
2--- |
[12,6] |
В |
2--- |
[8,3] |
В |