Приклад 3.1

Побудувати найкоротше остовне дерево для мережі, граф якої приведено на рис. 3.1.

Рисунок 3.1. – Граф мережі

Запишемо по наведеному графу матрицю вартостей (табл.3.1).

Табл. 3.1

Матриця вартостей

С

Вибираємо найменше значення C_ij (в прикладі [1]), відмічаємо рядки i та j ( в прикладі знаком *), а стовпці i та j викреслюємо і в подільшому не розглядаємо (в прикладі беремо в дужки (4), (6)). Серед значень C_ij, що входять в позначені рядки, вибираємо найменше, викреслюємо стовпець, в якому це найменше значення знаходиться, відмічаємо рядок з номером останнього викресленого стовпця і т.д. Алгоритм закінчує роботу, коли позначені всі рядки та викреслено всі стовпці.

1. S ={4,6}

С				(4)		(6)
		¥				¥	¥
	¥				¥	¥	¥
				¥	¥	¥	¥
			¥			[1]	¥	*
		¥	¥
	¥	¥	¥					*
	¥	¥	¥	¥

2. S ={4,5,6}

С				(4)	(5)	(6)
		¥				¥	¥
	¥				¥	¥	¥
				¥	¥	¥	¥
			¥			[1]	¥	*
		¥	¥					*
	¥	¥	¥		[2]			*
	¥	¥	¥	¥

3. S ={4,5,6,7}

С				(4)	(5)	(6)	(7)
						[1]		*
							[2]	*
					[2]			*
								*

4. S ={1,4,5,6,7}

С	(1)			(4)	(5)	(6)	(7)
								*
	[3]					[1]		*
							[2]	*
					[2]			*
								*

5. S ={1,3,4,5,6,7}

С	(1)		(3)	(4)	(5)	(6)	(7)
		¥	[2]			¥	¥	*
	¥				¥	¥	¥
	[2]			¥	¥	¥	¥	*
	[3]		¥			[1]	¥	*
		¥	¥				[2]	*
	¥	¥	¥		[2]			*
	¥	¥	¥	¥				*

6. S ={1,2,3,4,5,6,7}

С	(1)	(2)	(3)	(4)	(5)	(6)	(7)
			[2]					*
								*
	[2]							*
	[3]					[1]		*
							[2]	*
					[2]			*
								*

Довжина найкоротшого остовного дерева:

L=1+2+2+3+2+3=13.