Próbuję napisać algorytm, który znalazłby k1,3 czyli w jakimś grafie wierzchołek o stopniu trzy, do którego połączone są 3 wierzchołki o stopniu 1 czyli połączone tylko z nim.
Studiowałem ten algorytm przez 2 godziny i nadal nie mogę sobie poradzić ze znalezieniem problemu więc pomyślałem, że ktoś bardziej doświadczony mógłby mi w tym pomóc.
x=y=z=0;
k13=b=c=d=0;
a=-1;
for(k=0;k<rep;k++) //sprawdza każdy graf
{
for(i=0;i<n;i++){ //sprawdza każdą kolumnę
for(j=0;j<n;j++){ //sprawdza każdy wiersz
d+=tab[k][i][j]; //jeżeli krawędź lub i=j dodaje 1 do d
if(j==n-1){ //jeżeli cały wiersz sprawdzony
if(d==4){ //oraz d wynosi 4 czyli stopień wierzchołka i = 3
for(j=0;j<n;j++){ //to sprawdza kolumnę jeszcze raz
if(j!=i && tab[k][i][j]==1){ //jeżeli krawędź
if(a==-1)
a=x=j; //to a = pierwszy wierzchołek
else if(b==0)
b=y=j; //b = drugi wierzchołek
else
c=z=j; //c = trzeci wierzchołek
}
}
d=0;
for(j=0;j<n;j++) //dla wierzchołków a,b,c liczy stopnie
if(tab[k][a][j]==1) d+=1;
if(d==2) a=1;
else a=0;
d=0;
for(j=0;j<n;j++)
if(tab[k][b][j]==1) d+=1;
if(d==2) b=1;
else b=0;
d=0;
for(j=0;j<n;j++)
if(tab[k][c][j]==1) d+=1;
if(d==2) c=1;
else c=0;
d=0;
if(a==1 && b==1 && c==1) {
k13+=1; //jeśli suma stopni = 3, k13 został znaleziony
printf("k:%d i:%d a:%d b:%d c:%d\n", k+1, i, x, y, z);
b=c=d=0; //resetuje zmienne dla kolejnych poszukiwań
a=-1; //pierwszy wierchołek musi mieć wartość początkową różną od zera
//ponieważ tablice są indeksowane od zera
x=y=z=0;
}
}
d=0;
}
}
}
}
trochę niepotrzebnych zmiennych, które miały mi pomóc w rozwiązaniu problemu...
Ogólnie to są to grafy losowane w tablicy 3-wymiarowej. Wymiar pierwszy (k) to po prostu ilość grafów, a kolejne dwa wymiary definiują tablicę dwuwymiarową.
Zamysł tego algorytmu był taki, że najpierw szuka wierzchołka o stopniu 3. Jako zmienne a,b,c ustawia wierzchołki połączone do tego o stopniu 3 i sprawdza czy każdy z nich jest stopnia pierwszego. Jeśli tak dolicza kolejny k1,3 do zmiennej.