Z okazji sesji poprawkowej zostałem poproszony o pomoc przy jednym zagadnieniu: wyznaczenie planarności grafów. Poniższy kod jest wynikiem tej pomocy (nie jest on może idealny, ale stanowi punkt startu dla bardziej rozbudowanego programu).
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
const int Max_rozmiar = 100; // maksymalny rozmiar grafu
int graf[Max_rozmiar][Max_rozmiar]; //tablica polaczen pomiedzy
// wierzcholkami graf[x][y] = 1-jest
// graf[x][y] = 0 brak polaczenia
int stopien[Max_rozmiar]; // tablica zawiera stopnie wierzcholkow
int rozmiar; // rozmiar grafu;
// Deklaracje funkcji
void losuj_graf(float stopien_pelnosci); // losowo inicju polaczenia w grafie
void zeruj_graf(); // zeruje polaczenia w grafie
void wyswietl(); // wyswietls polaczenia grafu na ekranie
int redukcja(); // usuwa z grafu wszystki krawedzie o
// stopniu mniejszym niz 3 gdy nie wplywaja one na planarnosc
int znajdzK5(); // znajduje podraf K5
int znajdzK33(); // znajduje podraf K3,3
int planarnosc(); // sprawdza czy graf jest planarny
// Definicje funkcji
void losuj_graf(float stopien_pelnosci){
if ( (stopien_pelnosci >1 ) || (stopien_pelnosci <= 0 ))
{
printf("stopien pelnosci musi byc z przedzialu (0,1>\n");
return;
}
int i,j;
for(i=1;i<rozmiar;i++)
for(j=0;j<i;j++)
if ( rand() / (double)RAND_MAX < stopien_pelnosci) {graf[i][j] = 1;
graf[j][i] = 1;
stopien[i] += 1; // aktualizacja stopnia wierzcholka
stopien[j] += 1;
}
else {
graf[i][j] = 0;
graf[j][i] = 0;
}
}
void zeruj_graf(){
int i,j;
for(i=0;i<Max_rozmiar;i++){
stopien[i] = 0;
for(j=0;j<Max_rozmiar;j++)
graf[i][j] = 0;
}
}
void wyswietl(){
int i,j;
if (rozmiar >20){
printf("Rozmiar grafu wynosi %i i moze sie nie zmiescic",rozmiar);
printf(" na erkranie,\ndlatego nie bedzie wyswietlony\n");
return;
}
printf("Oto polaczenia w grafie.\n");
printf("1 - istnieje polaczenie.\n");
printf("0 - brak polaczenia.\n");
printf("W nawiasie podano stopien wierzcholka.\n\n ");
for(i=0;i<rozmiar-1;i++) printf("%2i ",i+1);
printf("\n");
for(i=0;i<rozmiar;i++){
printf("%2i(%2i) ",i+1,stopien[i]);
for(j=0;j<i;j++)
printf("%2i ",graf[i][j]);
printf("\n");
}
}
// funkcja usuwa z grafu wszystki wierzcholki stopnia 1 i 2
// poniewaz nie wplywaja one na planarnosc grafu
int redukcja(){
// zliczanie ilosc polaczeń wierzcholka
int i,j,k,l;
int zmiany = 0; //zmienna czy funkcja zmienia graf
for (i=0;i<rozmiar;i++){
if (stopien[i] == 1)
{
k = 0;
while (graf[i][k] == 0) k++; // znajdujemy jedynego sasiada
// usuwamy polaczenia
graf[i][k] = 0;
graf[k][i] = 0;
stopien[k] -= 1;
}
if (stopien[i] == 2){
k=0;
while (graf[i][k] == 0) k++;
l=k+1;
while (graf[i][l] == 0) l++;
// usuwamy polaczenia
graf[i][k] = 0; graf[k][i] = 0;
graf[i][l] = 0; graf[l][i] = 0;
// uaktualniamy stopien wierzcholkow
if (graf[k][l] == 1) {
stopien[k] -= 1;
stopien[l] -= 1;
}
// dodajemy polaczenie
graf[k][l] = 1; graf[l][k] = 1;
}
if (stopien[i] < 3)
{
// usuwamy wierzcholek z grafu
// ostania kolomna zastepuje kolumne i
for (j=0;j<rozmiar;j++) graf[i][j] = graf[rozmiar-1][j];
// ostani wiersz zastepuje wiersz i
for (j=0;j<rozmiar;j++) graf[j][i] = graf[j][rozmiar-1];
stopien[i] = stopien[rozmiar-1];
rozmiar -= 1;
i -= 1;
// zaznaczamy, ze dokonalismy zmian
zmiany = 1;
}
}
return zmiany;
}
int znajdzK5(){
int i1,i2,i3,i4,i5;
// przeszukujemy kolejno wszystkie piatki
for (i1=0;i1<rozmiar-4;i1++)
for (i2=i1+1;i2<rozmiar-3;i2++)
if (graf[i2][i1] == 1)
for (i3=i2+1;i3<rozmiar-2;i3++)
if ((graf[i3][i1]==1)&&(graf[i3][i2]==1))
for (i4=i3+1;i4<rozmiar-1;i4++)
if ((graf[i4][i1] == 1)&&(graf[i4][i2] == 1)&&(graf[i4][i3] == 1))
for (i5=i4+1;i5<rozmiar;i5++)
if ( (graf[i5][i1]==1)&&(graf[i5][i2]==1)&&
(graf[i5][i3]==1)&&(graf[i5][i4] == 1) )
{
return 1; // znaleziono podgraf K5
}
return 0;
}
int znajdzK33(){
int i1,i2,i3; // pierwsza trojka
int j1,j2,j3; // druga trojka
for(i1=0;i1<rozmiar-2;i1++)
for(i2=i1+1;i2<rozmiar-1;i2++)
for(i3=i2+1;i3<rozmiar;i3++)
{
for(j1=0;j1<rozmiar-2;j1++)
if((j1!=i1)&&(j1!=i2)&&(j1!=i3))
if((graf[j1][i1]==1)&&(graf[j1][i2]==1)&&(graf[j1][i3]==1))
for(j2=j1+1;j2<rozmiar-1;j2++)
if((j2!=i1)&&(j2!=i2)&&(j2!=i3))
if((graf[j2][i1]==1)&&(graf[j2][i2]==1)&&(graf[j2][i3]==1))
for(j3=j2+1;j3<rozmiar;j3++)
if((j3!=i1)&&(j3!=i2)&&(j3!=i3))
if((graf[j3][i1]==1)&&(graf[j3][i2]==1)&&(graf[j3][i3]==1))
{
return 1; // znaleziono podgraf K3,3
}
}
return 0;
}
int planarnosc(){
if (rozmiar <5) {
printf("Graf jest planarny poniewaz po redukcji\notrzymano ");
printf("graf o mniej niz 5 wierzcholkach\n");
printf("wszystkie grafy o mniej");
printf(" niz 5 wierzcholkach sa planarne\n");
return 1;
}
if ( znajdzK5() == 1) {
printf("Graf nie jest planarny poniewaz ");
printf("istnieje podgraf homeorficzny z K5\n");
return 0;
}
if ( znajdzK33() )
{
printf("Graf nie jest planarny poniewaz ");
printf("istnieje podgraf homeorficzny z K3,3\n");
return 0;
}
// Zgodnie z twierdzeniem kuratowskiego gdy nie znalezlismy podgrafow
// k3,3 i k5 w zredukowanym grafie graf jest planarny
printf("Graf jest planarny poniewaz ");
printf("nie istnieje zaden podgraf homeorficzny z K3,3 lub K5\n");
return 1;
}
void main(){
float p; // prawdopodobienstwo
int koniec = 0;
char c;
//inicjacja generatora liczb losowych
srand( (unsigned)time( NULL ) );
while(koniec == 0)
{
clrscr(); //czyszczenie ekranu
rozmiar = 0;
p = 0;
zeruj_graf();
// pobieramy dane grafu
printf("Podaj rozmiar grafu (2-%d)\n",Max_rozmiar);
scanf("%i",&rozmiar);
while ( (rozmiar<2)||(rozmiar>Max_rozmiar) ){
printf("Podales zly rozmiar grafu.");
printf("Podaj rozmiar grafu (2-%d) jeszcze raz\n",Max_rozmiar);
getchar();
scanf("%i",&rozmiar);
}
printf("Rozmiar grafu: %d\n",rozmiar);
printf("Podaj prawdopodobienstwo wystapienia krawedzi z przedzilu (0-1)\n");
printf("Aby rozlosowac polaczenia grafu\n");
scanf("%f",&p);
while ( (p <= 0)||(p>1) ){
printf("Podales zle wartosc prawdopodobienstwa.\nSprobuj jeszcze raz\n");
getchar();
scanf("%f",&p);
}
printf("Prawdopodobienstwo wystapienia krawedzi: %f\n",p);
losuj_graf(p); // losujemy polaczenia w grafie
wyswietl(); // wyswietlamy graf o ile nie jest za duzy
while (redukcja()); // usuwamy wszystkie wierzcholki stopnia 0,1,2
// ktore nie maja wplywy na planarnos
planarnosc(); // sprawdzamy plnarnosc
printf("Czy kontynuowac ? (t/n)\n");
getchar();
c = getchar();
if ( (c== 'n')||(c == 'N') ) koniec = 1;
}
}