Sito5: Różnice pomiędzy wersjami

Z PUTwiki
Przejdź do nawigacjiPrzejdź do wyszukiwania
Utworzono nową stronę "==== Spójne grafy całkowite rzędu $n = 15$ ==== * ok:grafy_calkowite * $n = 14$ -> ok:gcs14:14 * $n = 16$ -> ok:gcs16:16 * {{ :ok:gcs15:test15.zip |}} ^ Liczba wszystkich grafów rzędu $n=15$ ^ | 31426485969804308768 | Wielkość przestrzeni: ${{{n=15} \choose {2}} \choose {k}} = {{105} \choose {k}} $ * https://www.wolframalpha.com/input?i=binomial+calculator | $k$ | spójnych | # grafów całkowitych…"
 
m 1 wersja
 
(Brak różnic)

Aktualna wersja na dzień 21:22, 8 gru 2025

Spójne grafy całkowite rzędu $n = 15$

[edytuj | edytuj kod]
 * ok:grafy_calkowite
 * $n = 14$  -> ok:gcs14:14
 * $n = 16$  -> ok:gcs16:16
 * Ok:gcs15:test15.zip

^ Liczba wszystkich grafów rzędu $n=15$ ^ | [[1]] |

Wielkość przestrzeni: ${{{n=15} \choose {2}} \choose {k}} = {{105} \choose {k}} $ 

 * [[2]]

| $k$ | spójnych | # grafów całkowitych spójnych | czas | | 14 | 7741 | 0 | | 15 | 110381 | 0 | | 16 | 959374 | 0 | | 17 | 6499706 | 1 | 24 min | | 18 | | 3 | | 19 | | 6 | | 20 | | 4 | | 21 | | 5 | 1h | | 22 | | ? | | ... | | | | 27 | | ? | | ... | | | | 30 | | ? | | 31 | | ? | | 32 | | ? | | 33 | | ? | | ... | | | | 41 | | ? | | ... | | | | 45 | | ? | | ... | | | | 56 | | ? | ... | | | | 60 | | ? | | ... | | | | 75 | | ? | | ... | | | | 87 | | ? | | 88 | 39500164 | 1 | | 89 | 10176658 | 4 | | 90 | 2632419 | 4 | | 91 | | 0 | | 92 | | 0 | | 93 | | 0 | | 94 | | 0 | | 95 | | 0 | | 96 | | 0 | | 97 | 496 | 1 | | 98 | | 0 | | 99 | | 0 | | 100 | | 0 | | 101 | | 0 | | 102 | | 0 | | 103 | | 0 | | 104 | | 0 | | $ {{15} \choose {2}} = $ 105 | 1 | 1 |


| $Sp(K_{3,12}) = \left[6,0^{(13)},-6\right]$ |


Skrypt 15

[edytuj | edytuj kod]
 * ok:nauty
 * ok:sito#sito_5 Kompilacja: gcc -O3 sito5.c -o sito5 -fopenmp -lm
 * chmod 777 calkowite15.sh

<file bash calkowite15.sh>

  1. !/bin/bash
  2. KTZ 2025
  3. plik: calkowite15.sh
  4. ./calkowite15.sh 15 21 $((2**31)) 0

n=$1 e=$2 mod=$3 pierwszy=$4

echo czas: $(date)

for (( res=$pierwszy; res < $mod ; res+=1 )) do 

echo "time ./geng -c $n $e:$e $res/$mod 2>/dev/null | ./sito5 640000 | tee -a wynik$n_$e.txt"
echo "./calkowite15.sh $n $e $mod $res" > ktz2025_todo$n_$e.sh
time ./geng -c $n $e:$e $res/$mod 2>/dev/null | ./sito5 640000 | tee -a wynik$n_$e.txt

done

echo czas: $(date) echo "# wszystko zrobione " > ktz2025_todo$n_$e.sh

</file>

$./calkowite15.sh 15 21 $((2**31)) 0 $ cat wynik15_25.txt $ cat ktz2025_todo15_21.sh 

 * **Uwagi KTZ**: 
   * Jeżeli wartość zmiennej mod jest zbyt mała, to wówczas przetwarzanie może długo trwać.
     * Maksymalna wartość mod to 2147483647. 
   * Może być tak, że większość zadań wykonuje się krótko, jednak są podzadania, które wykonują się bardzo długo. Można przerwać i pominąć takie podzadanie (i zapisać jego parametry aby można było to przeszukać później).
   * Dobrze byłoby też zapisać parametry i czasy wykonania w przypadku wyszukania grafu całkowitego przez dane podzadanie.

Dane

[edytuj | edytuj kod]

15 000001001010100110000001100100000100011000001001001001010000011000010000110010001110100001000000101000000 274 25 25 175 274 175 184 214 94 344 184 244 184 144 124 95 274 344 344 175 116 269 94 25 95 175 254 95 251 269 15 001000010001010001100000011011011000000000011100000010010010100010000010001000001100000000110100000101001 66 344 302 294 145 25 66 284 225 25 145 85 76 244 185 55 25 284 305 255 225 85 251 314 127 314 344 294 302 344 15 101000000000110000001010100011100000100100100100001000000010101000000001010000110001001100010010010100001 94 94 245 185 25 313 274 94 145 185 84 284 84 344 274 25 294 284 195 185 333 64 294 344 344 314 25 64 94 25 15 000011101000000010000001100001100001000100101001000000000000000000000000000001000000100011000001011000000 265 165 25 235 265 295 25 15 15 165 245 235 285 235 245 95 65 95 285 15 65 235 45 295 35 165 55 165 75 165 15 000001001010100110000001100100000100011000001001001001010000011000010000110010001110100001000000101000000 274 25 25 175 274 175 184 214 94 344 184 244 184 144 124 95 274 344 344 175 116 269 94 25 95 175 254 95 251 269 15 001000010001010001100000011011011000000000011100000010010010100010000010001000001100000000110100000101001 66 344 302 294 145 25 66 284 225 25 145 85 76 244 185 55 25 284 305 255 225 85 251 314 127 314 344 294 302 344 15 101000000000110000001010100011100000100100100100001000000010101000000001010000110001001100010010010100001 94 94 245 185 25 313 274 94 145 185 84 284 84 344 274 25 294 284 195 185 333 64 294 344 344 314 25 64 94 25 15 000001001110000000100110100000010100011000100100110001001110001001101001100000000011001100000000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000001001000110000100011100000010101001000100101100001101100001010011001100000001010000101000000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000001001010010000100010110000010100011000100111000001101100001010011001100000001010000101000000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000001001001100000100011001000010100011000100111000001101100001010011001100000001010000101000000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000001001110000000100000111000010111000000100001110001111000001000111001001000010010001001000000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000010110100000000100100011000010100101000010110100000111100000011010000001111000001001000001000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000010001000110000100100011000011110000000111010000000011011000011100000111000000110000101000000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000010001000110000100100011000011001010000110001100000101101000011100000111001010000010000000010000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000011001001000000110011000000010000111000011110000001000111000000111001100000001010010001010000000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000011000110000001010010100000101000110000101000110001101001000011000000100100000101001100000110000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000011000011000001010011000000101010001000101000110001100110000010100000110000001010000011001010000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 000101000101000001001011000000110001001000011001100010010010000110001000011000000011001010001010000000000 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 

 * $ K_3 \times G_5 $ -- iloczyn kartezjański grafów całkowitych rzędu 5 i grafu $K_3$


15 000000000000010000000000001000000100000000000100000010000000001000000000010100000010000010001010101101100 150 290 206 277 254 243 283 193 289 136 271 81 232 37 179 14 121 14 68 37 29 80 11 136 17 193 46 243 94 277 15 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 250 150 241 190 216 224 180 245 140 249 100 236 70 208 53 170 53 130 70 92 101 64 140 51 180 55 216 76 241 110 15 001111111111110111111111111111111111111001111111110111111111111111111001111110111111111111001110111111000 250 150 241 190 216 224 180 245 140 249 100 236 70 208 53 170 53 130 70 92 101 64 140 51 180 55 216 76 241 110

15 111001111111110011111111111000000000000000000000000000000000000000000000000000000000000000000000000000000 15 165 295 165 15 25 15 285 295 295 295 25 145 185 145 205 145 225 145 245 145 145 145 125 145 105 145 85 145 65

Grafy dwudzielne

[edytuj | edytuj kod]

$ ../genbg -c 1 14 -l | ./sito3 8000 >A ../genbg n=1+14 e=14:14 d=1:1 D=14:1 c >Z 1 graphs generated in 0.00 sec | Czas(OpenMP): | 0.005757[sec] |

$ ../genbg -c 2 13 -l | ./sito3 8000 >A ../genbg n=2+13 e=14:26 d=1:1 D=13:2 c >Z 49 graphs generated in 0.00 sec | Czas(OpenMP): | 0.005799[sec] |

$ ../genbg -c 3 12 -l | ./sito3 8000 >A ../genbg n=3+12 e=14:36 d=1:1 D=12:3 c >Z 3171 graphs generated in 0.09 sec N@G`@?_G@?[?w?w?[?? NErEDA_gD?K?W?W?K?? NFzfFB_wF?[?w?w?[?? | Czas(OpenMP): | 0.095876[sec] |

$ ../genbg -c 4 11 -l | ./sito3 8000 >A ../genbg n=4+11 e=14:44 d=1:1 D=11:4 c N?G`@?_gB?W?w?{?]?? N?CO`b?wF_]?{?{?]?? N?CO_a?O@?[?{?{?]?? N?CP@?_K@_Q?S?o?[?? N?G___oKF?[?s?s?]?? >Z 195862 graphs generated in 2.27 sec | Czas(OpenMP): | 2.460899[sec] |

$ ../genbg -c 5 10 -l | ./sito3 8000 >A ../genbg n=5+10 e=14:50 d=1:1 D=10:5 c N??GT@OSD?F?M?{?^?? N??G__OECOH?I?w?]?? N??`?_GgB?[?]?]?N?? N??GOb?I@OE?K?K?[?? N??pOr?M@oV?]?}?^?? >Z 7468313 graphs generated in 42.20 sec | Czas(OpenMP): | 48.617348[sec] |

$ ../genbg -c 6 9 -l | ./sito3 8000 >A ../genbg n=6+9 e=14:54 d=1:1 D=9:6 c N???GGC@?G^_~?~?^_? N???GGC@?oB?v?n?N_? N???GGKBEGX?q?|?]_? N???GJ?pEGF_{?y?Z?? N???GHSJ@WI_w?x?[_? N???GG[FCoJ?M?x?^?? N???GG_C?OF_N?}?^?? N???GGGE?oE_L?s?[?? N??@C@?oF?]?y?x?F_? N???G_G`AGW_x?u?^_? N??CA?_E?g@_w?~?^_? N???OGK{@wF_n?^?^_? N???GR?D?gB?I?M?]?? N???OGoK@_E?K?N?^_? N???OIOWF_R_Z?N?F_? N???OJGpAoS_{?{?X_? N??CCIC\BWJ_N?~?^_? N??CEA_c?WP_[?^?^_? N???HGSBE?^?~?~?^_? N??C@osJ?wZ_v?^?N_? N??@`_KB@w\?y?t?Y_? N???ogKZBWL_v?n?N_? N???kHCH?oB?B?B?]?? N??CIGcE?oB_F?}?^?? N??@`OSB@w]?y?t?X_? N???gXWMCwN?]?^?^_? N??Cc`GH@GH?w?F?B_? N??E?w[JDWL_v?v?\_? N??C[XcT@g^?}?}?^?? >Z 110381781 graphs generated in 427.03 sec | Czas(OpenMP): | 565.450493[sec] |

$ ../genbg -c 7 8 -l | ./sito3 8000 >A ../genbg n=7+8 e=14:56 d=1:1 D=8:7 c N????CAB_[F?L?f_Jo? N???@?O?_CWOQ_P_]?? N????CG@?S?o{?M_Wo? N????CCAE?@_{?M_X_? N????_G@CCGOG_F?^_? N????OC?_[]?~_~_^o? N???C?C`F?[_p_h_^?? N????GAQ@_T?e?R_Eo? N????CCp@KOoP_v?[o? N????GAuDoN?^_^_No? N????CaCe?EO{?]_Mo? N???CAGqf_]_|?}?^_? N????GaC_S?oM?p?^?? N???CB?WA_WO{?{_N_? N???A?gDcgTOb_{?^_? ...

$ ../../genbg -c 7 8 -l 0/8 | ../sito3 8000 | tee -a raport.txt >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=0/8 >Z 57347388 graphs generated in 200.00 sec | Czas(OpenMP): | 245.556048[sec] | N????CG@?S?o{?M_Wo? N????CCAE?@_{?M_X_? N????GAuDoN?^_^_No? N???A?gDcgTOb_{?^_? N????oWw@cDOM_f?^?? N????SSeASDOF_F_^?? N????cKwFc\_v_n_No?

$ ../../genbg -c 7 8 -l 1/8 | ../sito3 8000 | tee -a raport.txt >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=1/8 >Z 57199702 graphs generated in 198.89 sec | Czas(OpenMP): | 245.428732[sec] | N????CAB_[F?L?f_Jo? N???C?C`F?[_p_h_^?? N???CAGqf_]_|?}?^_?

$ ../../genbg -c 7 8 -l 2/8 | ../sito3 8000 | tee -a raport.txt >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=2/8 >Z 57234194 graphs generated in 203.47 sec | Czas(OpenMP): | 248.722466[sec] | N????CCp@KOoP_v?[o? N????KEEEKL_Y_F_Bo? N????KEEEKMOY_F_Bo?


$ ../../genbg -c 7 8 -l 3/8 | ../sito3 8000 1> >(tee -a raport.txt) 2> >(tee -a raport.txt) >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=3/8 >Z 57171360 graphs generated in 198.80 sec N????GAQ@_T?e?R_Eo? N????CaCe?EO{?]_Mo? N????KEEEKTOY_F_Bo? | Czas(OpenMP): | 245.489194[sec] |

$ ../../genbg -c 7 8 -l 4/8 | ../sito3 8000 1> >(tee -a raport.txt) 2> >(tee -a raport.txt) >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=4/8 >Z 56928298 graphs generated in 194.66 sec N????OC?_[]?~_~_^o? N????GaC_S?oM?p?^?? | Czas(OpenMP): | 251.913929[sec] |


$ ../../genbg -c 7 8 -l 5/8 | ../sito3 8000 1> >(tee -a raport.txt) 2> >(tee -a raport.txt) >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=5/8 >Z 56985930 graphs generated in 199.62 sec N????_G@CCGOG_F?^_? N???CB?WA_WO{?{_N_? N????[MD_kU_Y_[_T_? N???CME`b_L?U?M?^o? | Czas(OpenMP): | 257.134981[sec] |

$ ../../genbg -c 7 8 -l 6/8 | ../sito3 8000 1> >(tee -a raport.txt) 2> >(tee -a raport.txt) >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=6/8 >Z 57292259 graphs generated in 201.98 sec N???@?O?_CWOQ_P_]?? N????WI@_[@o{?{?^o? N???@aCqDGQ_l?p_^?? | Czas(OpenMP): | 258.055991[sec] |


$ ../../genbg -c 7 8 -l 7/8 | ../sito3 8000 1> >(tee -a raport.txt) 2> >(tee -a raport.txt) >A ../../genbg n=7+8 e=14:56 d=1:1 D=8:7 c class=7/8 >Z 57043804 graphs generated in 202.38 sec N????WI@f_\ov_n_No? | Czas(OpenMP): | 265.643800[sec] |

Zliczanie

[edytuj | edytuj kod]
 * Zobacz: ok:problemy_zliczania

^ $e$ - liczba krawędzi ^ liczba grafów ^ ${{105} \choose {e}} $ ^ | 0 | 1 | | 1 | 1 | | 2 | 2 | | 3 | 5 | | 4 | 11 | | 5 | 26 | | 6 | 68 | | 7 | 177 | | 8 | 496 | | 9 | 1471 | | 10 | 4583 | | 11 | 15036 | | 12 | 51814 | | 13 | 185987 | | 14 | 691001 | | 15 | 2632420 | | 16 | 10176660 | | 17 | 39500169 | | 18 | 152374465 | | 19 | 578891716 | | 20 | 2149523582 | | 21 | 7753406889 | | 22 | 27040032015 | 24384496062806414644200 | | 23 | 90859878747 | 87996224922301409368200 | | 24 | 293429720936 | | 25 | 909199479603 | | 26 | 2699941862354 | | 27 | 7678976881470 | | 28 | 20910536197366 | | 29 | 54513628209893 | | 30 | 136070590191317 | | 31 | 325264684039708 | | 32 | 744823014518211 | | 33 | 1634428386201309 | | 34 | 3438285431507061 | | 35 | 6936720574597423 | | 36 | 13426937977152944 | | 37 | 24944913304587039 | | 38 | 44497508446112065 | | 39 | 76242525660396354 | | 40 | 125521270445592815 | | 41 | 198626349980261157 | | 42 | 302194587531738164 | | 43 | 442167645425634116 | | 44 | 622367640359865212 | | 45 | 842878760010352632 | | 46 | 1098571996084797125 | | 47 | 1378203771448328912 | | 48 | 1664504614806849040 | | 49 | 1935518921253340732 | | 50 | 2167174862664381524 | | 51 | 2336721756356087856 | | 52 | **2426376196165902704** | | 53 | **2426376196165902704** | | 54 | 2336721756356087856 | | 55 | 2167174862664381524 | | 56 | 1935518921253340732 | | 57 | 1664504614806849040 | | 58 | 1378203771448328912 | | 59 | 1098571996084797125 | | 60 | 842878760010352632 | | 61 | 622367640359865212 | | 62 | 442167645425634116 | | 63 | 302194587531738164 | | 64 | 198626349980261157 | | 65 | 125521270445592815 | | 66 | 76242525660396354 | | 67 | 44497508446112065 | | 68 | 24944913304587039 | | 69 | 13426937977152944 | | 70 | 6936720574597423 | | 71 | 3438285431507061 | | 72 | 1634428386201309 | | 73 | 744823014518211 | | 74 | 325264684039708 | | 75 | 136070590191317 | | 76 | 54513628209893 | | 77 | 20910536197366 | | 78 | 7678976881470 | | 79 | 2699941862354 | | 80 | 909199479603 | | 81 | 293429720936 | | 82 | 90859878747 | | 83 | 27040032015 | | 84 | 7753406889 | | 85 | 2149523582 | | 86 | 578891716 | | 87 | 152374465 | | 88 | 39500169 | | 89 | 10176660 | | 90 | 2632420 | | 91 | 691001 | | 92 | 185987 | | 93 | 51814 | | 94 | 15036 | | 95 | 4583 | | 96 | 1471 | | 97 | 496 | | 98 | 177 | | 99 | 68 | | 100 | 26 | | 101 | 11 | | 102 | 5 | | 103 | 2 | | 104 | 1 | | 105 | 1 | | Razem: | 31 426 485 969 804 308 768 | | | | 31 [[3]] grafów; $10^{18}$ | |

d:\fgrafy\cgrafy\test\python>type g9_24.graph6 | python net6.py 6 NwCW?CB18:01, 24 lis 2025 (UTC)18:01, 24 lis 2025 (UTC)~w NwCGGCP18:01, 24 lis 2025 (UTC)18:01, 24 lis 2025 (UTC)~w

d:\fgrafy\cgrafy\test\python>type g12_325sort.graph6 | python net6.py 3 N^~nm|^nfq{{18:01, 24 lis 2025 (UTC)~w NJ^~{qhk]Fwn18:01, 24 lis 2025 (UTC)~w NJ^~{qXw^Bo18:01, 24 lis 2025 (UTC)~~w NJ^v\VSq|jRN18:01, 24 lis 2025 (UTC)~w NJZ~sqjtUVum18:01, 24 lis 2025 (UTC)~w NJZ~sqjlUjx]18:01, 24 lis 2025 (UTC)~w NIR~vqwu|ZUt18:01, 24 lis 2025 (UTC)~w NBZ|vVX{ljXr18:01, 24 lis 2025 (UTC)~w NBZ|urj{s}[f18:01, 24 lis 2025 (UTC)~w NB??GKGAL?W?18:01, 24 lis 2025 (UTC)~w NB???KIBD?W?18:01, 24 lis 2025 (UTC)~w N?CX@D?OK?O@18:01, 24 lis 2025 (UTC)~w N???WWoKE?W?18:01, 24 lis 2025 (UTC)~w

d:\fgrafy\cgrafy\test\python>type g13_540.graph6 | python net6.py 2 Nzn]||~xfQ}FwF172.18.0.1 18:01, 24 lis 2025 (UTC)w

d:\fgrafy\cgrafy\test\python>type g3_1.graph6 | python net8.py 3 4 NFzf~z{172.18.0.1^{172.18.0.1 18:01, 24 lis 2025 (UTC)^~_

n = 15 L = 1

g10_83.graph6 5 1 N172.18.0.1 18:01, 24 lis 2025 (UTC){??N~~}~{~{^}? N~{GhLF`172.18.0.1}~{~{^}?

n = 15 L = 2

g5_3.graph6 5 2 N?B~vrw}F~~}~{~{^}?

n = 15 L = 1

Źródło: „https://wiki.idzie.xn--t-wha.xn--drog-eta.pl/index.php?title=Sito5&oldid=3370”