(* La matrice d'adjacence "graph" du graphe est representee par N tableaux de listes. Soit [2; 3; 4; 9] la liste en graph[18]. Cela veut dire que le sommet a l'indice 18 dans "graph" a pour voisins les sommets d'indices 2, 3, 4 et 9. Comme la matrice d'adjacence est symetrique, on trouvera l'indice 18 dans graph[2], graph[3], graph[4] et graph[9]. *) let n = 100;; let graph = [|[96; 84; 82; 78; 75; 68; 61; 55; 40; 26; 24; 21; 14; 13; 6]; [94; 93; 84; 80; 79; 75; 73; 69; 65; 62; 56; 52; 49; 42; 38; 19]; [98; 91; 81; 72; 63; 58; 44; 39; 34; 29; 28; 22; 11; 10; 7; 3]; [12; 66; 78; 98; 97; 91; 90; 88; 74; 63; 59; 58; 44; 39; 28; 25; 2]; [88; 59; 58; 54; 39; 36; 35; 20]; [83; 79; 69; 65; 52]; [96; 84; 82; 78; 75; 73; 61; 57; 55; 40; 26; 19; 14; 13; 0]; [15; 30; 48; 64; 82; 91; 89; 87; 76; 72; 63; 34; 31; 29; 22; 16; 12; 11; 10; 2]; [99; 97; 86; 71; 60; 59; 54; 53]; [99; 92; 70; 60; 51; 33; 23]; [91; 89; 83; 81; 76; 72; 34; 29; 16; 11; 7; 2]; [90; 98; 91; 89; 87; 76; 72; 66; 63; 50; 44; 29; 22; 16; 12; 10; 7; 2]; [3; 25; 78; 89; 87; 82; 66; 57; 50; 48; 31; 30; 22; 16; 11; 7]; [96; 84; 75; 62; 56; 26; 24; 19; 6; 0]; [96; 82; 78; 61; 55; 41; 40; 21; 6; 0]; [7; 16; 82; 95; 90; 87; 77; 66; 64; 63; 50; 47; 27; 25; 22]; [15; 27; 44; 48; 90; 91; 89; 87; 76; 72; 66; 63; 50; 31; 30; 22; 12; 11; 10; 7]; [99; 70; 67; 64; 51; 43; 33; 23]; [95; 82; 77; 48; 46; 45; 41]; [96; 93; 84; 80; 75; 73; 69; 65; 62; 57; 56; 55; 42; 38; 26; 13; 6; 1]; [71; 59; 54; 36; 35; 4]; [68; 61; 40; 14; 0]; [30; 57; 64; 78; 91; 90; 87; 72; 66; 63; 50; 44; 25; 16; 15; 12; 11; 7; 2]; [99; 92; 70; 60; 51; 33; 17; 9]; [96; 68; 26; 13; 0]; [12; 30; 31; 98; 97; 91; 90; 74; 67; 64; 63; 50; 44; 22; 15; 3]; [96; 84; 75; 62; 56; 40; 24; 19; 13; 6; 0]; [16; 63; 95; 90; 85; 77; 66; 64; 50; 47; 46; 45; 43; 32; 15]; [98; 91; 88; 81; 72; 58; 44; 39; 29; 3; 2]; [98; 91; 81; 76; 72; 34; 28; 11; 10; 7; 2]; [7; 22; 25; 50; 74; 91; 93; 89; 87; 82; 78; 73; 66; 57; 55; 48; 31; 16; 12]; [25; 64; 66; 93; 89; 87; 82; 78; 75; 73; 65; 57; 55; 48; 30; 16; 12; 7]; [95; 85; 77; 47; 46; 45; 43; 27]; [99; 92; 70; 51; 23; 17; 9]; [81; 76; 72; 29; 10; 7; 2]; [88; 71; 59; 54; 36; 20; 4]; [88; 71; 59; 54; 39; 35; 20; 4]; [94; 80; 79; 69; 49; 38]; [94; 84; 80; 69; 62; 56; 49; 42; 37; 19; 1]; [98; 88; 81; 59; 58; 44; 36; 28; 4; 3; 2]; [96; 84; 82; 78; 75; 61; 57; 55; 48; 41; 26; 21; 14; 6; 0]; [82; 78; 61; 48; 40; 18; 14]; [93; 89; 84; 83; 80; 75; 73; 69; 65; 62; 57; 52; 49; 38; 19; 1]; [95; 85; 64; 47; 45; 32; 27; 17]; [16; 78; 82; 98; 91; 81; 72; 63; 58; 50; 39; 28; 25; 22; 11; 3; 2]; [95; 85; 77; 47; 46; 43; 32; 27; 18]; [95; 85; 77; 45; 32; 27; 18]; [48; 74; 95; 90; 85; 77; 64; 45; 43; 32; 27; 15]; [7; 16; 47; 64; 87; 82; 78; 77; 66; 57; 55; 41; 40; 31; 30; 18; 12]; [94; 80; 79; 69; 65; 62; 56; 52; 42; 38; 37; 1]; [30; 91; 90; 87; 66; 63; 44; 27; 25; 22; 16; 15; 12; 11]; [99; 92; 70; 33; 23; 17; 9]; [93; 89; 83; 80; 79; 73; 69; 65; 49; 42; 5; 1]; [99; 86; 71; 60; 54; 8]; [86; 71; 60; 59; 53; 36; 35; 20; 8; 4]; [74; 93; 84; 82; 78; 75; 73; 57; 48; 40; 31; 30; 19; 14; 6; 0]; [96; 94; 84; 80; 62; 49; 38; 26; 19; 13; 1]; [22; 63; 91; 93; 89; 84; 82; 78; 75; 73; 55; 48; 42; 40; 31; 30; 19; 12; 6]; [98; 88; 81; 44; 39; 28; 4; 3; 2]; [97; 88; 86; 74; 71; 54; 39; 36; 35; 20; 8; 4; 3]; [99; 97; 86; 71; 70; 67; 54; 53; 23; 9; 8]; [82; 78; 68; 41; 40; 21; 14; 6; 0]; [96; 94; 84; 80; 75; 73; 69; 65; 56; 49; 42; 38; 26; 19; 13; 1]; [27; 57; 98; 91; 90; 87; 72; 66; 50; 44; 25; 22; 16; 15; 11; 7; 3; 2]; [7; 22; 31; 48; 78; 91; 90; 85; 74; 70; 67; 47; 43; 27; 25; 17; 15]; [93; 89; 84; 83; 80; 79; 75; 73; 69; 62; 52; 49; 42; 31; 19; 5; 1]; [3; 31; 78; 90; 87; 63; 50; 48; 30; 27; 22; 16; 15; 12; 11]; [99; 97; 90; 86; 74; 70; 64; 60; 25; 17]; [61; 24; 21; 0]; [94; 93; 83; 80; 79; 73; 65; 62; 52; 49; 42; 38; 37; 19; 5; 1]; [99; 86; 74; 67; 64; 60; 51; 33; 23; 17; 9]; [97; 86; 60; 59; 54; 53; 36; 35; 20; 8]; [98; 91; 81; 76; 63; 44; 34; 29; 28; 22; 16; 11; 10; 7; 2]; [93; 89; 84; 80; 75; 69; 65; 62; 57; 55; 52; 42; 31; 30; 19; 6; 1]; [30; 47; 55; 89; 97; 90; 86; 70; 67; 64; 59; 25; 3]; [96; 93; 84; 82; 78; 73; 65; 62; 57; 55; 42; 40; 31; 26; 19; 13; 6; 1; 0]; [89; 83; 72; 34; 29; 16; 11; 10; 7]; [95; 85; 48; 47; 46; 45; 32; 27; 18; 15]; [3; 12; 22; 44; 64; 66; 82; 75; 61; 57; 55; 48; 41; 40; 31; 30; 14; 6; 0]; [83; 80; 69; 65; 52; 49; 37; 5; 1]; [94; 93; 84; 79; 73; 69; 65; 62; 56; 52; 49; 42; 38; 37; 19; 1]; [98; 91; 72; 58; 44; 39; 34; 29; 28; 10; 2]; [7; 15; 44; 78; 75; 61; 57; 55; 48; 41; 40; 31; 30; 18; 14; 12; 6; 0]; [93; 89; 79; 76; 69; 65; 52; 42; 10; 5]; [96; 93; 80; 75; 73; 65; 62; 57; 56; 55; 42; 40; 38; 26; 19; 13; 6; 1; 0]; [95; 77; 64; 47; 46; 45; 43; 32; 27]; [99; 97; 74; 71; 70; 67; 60; 59; 54; 53; 8]; [91; 66; 63; 50; 48; 31; 30; 22; 16; 15; 12; 11; 7]; [59; 58; 39; 36; 35; 28; 4; 3]; [74; 90; 93; 83; 76; 73; 65; 57; 52; 42; 31; 30; 16; 12; 11; 10; 7]; [11; 16; 66; 89; 97; 74; 67; 64; 63; 50; 47; 27; 25; 22; 15; 3]; [30; 57; 64; 98; 87; 81; 72; 63; 50; 44; 29; 28; 25; 22; 16; 11; 10; 7; 3; 2]; [99; 51; 33; 23; 9]; [89; 84; 83; 80; 75; 73; 69; 65; 57; 55; 52; 42; 31; 30; 19; 1]; [80; 69; 62; 56; 49; 38; 37; 1]; [85; 77; 47; 46; 45; 43; 32; 27; 18; 15]; [84; 75; 62; 56; 40; 26; 24; 19; 14; 13; 6; 0]; [90; 86; 74; 71; 67; 60; 59; 25; 8; 3]; [91; 81; 72; 63; 58; 44; 39; 29; 28; 25; 11; 3; 2]; [92; 86; 70; 67; 60; 53; 51; 33; 23; 17; 9; 8]|];; (* La fonction "result" affiche sur la sortie standard le contenu d'un etiquetage donne. La chaine affichee est sous la forme "f1 - f2 - ... - fn", ou fi est l'etiquette associee au sommet d'indice i dans "graph". Vous pouvez copier-coller cette chaine dans le champ prevu a cet effet sur la page de l'enonce. *) let result f = for i = 0 to n - 2 do print_string (string_of_int f.(i) ^ " - "); done; print_endline (string_of_int f.(n - 1)) ;; (* La fonction "main" est le point d'entree du programme. Le code pre-ecrit initialise un etiquetage 1 - 2 - ... - N, et l'affiche via la fonction "result". *) let main () = let f = Array.init n (fun i -> i + 1) in result f ;; main ();;