Geek or not

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 12 avril 2006.
932 personnes ont affiché cette page et sa popularité est de 8.

Pebkac

Mots clefs

Prim

I see dead pixels.

Outils

SYN

Exercice 18

Réponses

On reconnait un problème de recherche d’arbre couvrant de coût minimal
Application de l’algorithme de Prim : [1]
$T=\lbrace B \rbrace$
$U' = \emptyset$

$U'=\lbrace (B,O) \rbrace$
$T = T + \lbrace O \rbrace = \lbrace B,O \rbrace$

	B	O	E	R	St L	L	N	C
B	-
O	$\not{5}$	-
E	18	17	-
R	9	11	27	-
St L	13	7	23	20	-
L	7	12	15	15	15	-
N	38	38	20	40	40	35	-
C	22	15	25	25	30	10	45	-

$U'=\lbrace (B,O),(O,S^tL) \rbrace$
$T = \lbrace B,O,S^tL \rbrace$

B	O	E	R	St L	L	N	C
B	-
O	$\not{5}$	-
E	18	17	-
R	9	11	27	-
St L	$\not{13}$	$\not{7}$	23	20	-
L	7	12	15	15	15	-
N	38	38	20	40	40	35	-
C	22	15	25	25	30	10	45	-

$U'=\lbrace (B,O),(O,S^tL),(B,L) \rbrace$
$T = \lbrace B,O,S^tL,L \rbrace$

	B	O	E	R	St L	L	N	C
B	-
O	$\not{5}$	-
E	18	17	-
R	9	11	27	-
St L	$\not{13}$	$\not{7}$	23	20	-
L	$\not{7}$	$\not{12}$	15	15	$\not{15}$	-
N	38	38	20	40	40	35	-
C	22	15	25	25	30	10	45	-

$U'=\lbrace (B,O),(O,S^tL),(B,L),(B,R) \rbrace$
$T = \lbrace B,O,S^tL,L,R \rbrace$

B	O	E	R	StL	L	N	C
B	-
O	$\not{5}$	-
E	18	17	-
R	$\not{9}$	$\not{11}$	27	-
St L	$\not{13}$	$\not{7}$	23	$\not{20}$	-
L	$\not{7}$	$\not{12}$	15	$\not{15}$	$\not{15}$	-
N	38	38	20	40	40	35	-
C	22	15	25	25	30	10	45	-

$U'=\lbrace (B,O),(O,S^tL),(B,L),(B,R),(L,C) \rbrace$
$T = \lbrace B,O,S^tL,L,R,C \rbrace$

B	O	E	R	St L	L	N	C
B	-
O	$\not{5}$	-
E	18	17	-
R	$\not{9}$	$\not{11}$	27	-
St L	$\not{13}$	$\not{7}$	23	$\not{20}$	-
L	$\not{7}$	$\not{12}$	15	$\not{15}$	$\not{15}$	-
N	38	38	20	40	40	35	-
C	$\not{22}$	$\not{15}$	25	$\not{25}$	$\not{30}$	$\not{10}$	45	-

$U'=\lbrace (B,O),(O,S^tL),(B,L),(B,R),(L,C),(L,E) \rbrace$
$T = \lbrace B,O,S^tL,L,R,C,E \rbrace$

B	O	E	R	St L	L	N	C
B	-
O	$\not{5}$	-
E	$\not{18}$	$\not{17}$	-
R	$\not{9}$	$\not{11}$	$\not{27}$	-
St L	$\not{13}$	$\not{7}$	$\not{23}$	$\not{20}$	-
L	$\not{7}$	$\not{12}$	$\not{15}$	$\not{15}$	$\not{15}$	-
N	38	38	20	40	40	35	-
C	$\not{22}$	$\not{15}$	$\not{25}$	$\not{25}$	$\not{30}$	$\not{10}$	45	-

$U'=\lbrace (B,O),(O,S^tL),(B,L),(B,R),(L,C),(L,E),(E,N) \rbrace$
$T = \lbrace B,O,S^tL,L,R,C,E,N \rbrace$

	B	O	E	R	$S^{t}$ L	L	N	C
B	-
O	$\not{5}$	-
E	$\not{18}$	$\not{17}$	-
R	$\not9$	$\not{11}$	$\not{27}$	-
$S^{t}$	$\not{13}$	$\not7$	$\not{23}$	$\not{20}$	-
L	$\not{7}$	$\not{12}$	$\not{15}$	$\not{15}$	$\not{15}$	-
N	$\not{38}$	$\not{38}$	$\not{20}$	$\not{40}$	$\not{40}$	$\not{35}$	-
C	$\not{22}$	$\not{15}$	$\not{25}$	$\not{25}$	$\not{30}$	$\not{10}$	$\not{45}$	-

On obtient donc finalement un arbre couvrant de coût égal à 73 de la forme :


Arbre couvrant déduit de l’algorithme de Prim

pages : << 1 2

[1] On va barrer, au fur et a mesure que l’on ajoute des sommets dans la liste $U'$ , des coûts dans le tableau correspondant aux liens existants entre tous les sommets de la liste $U'$

Poster un message