Teoria grafurilor și combinatorică

Se considera matricea booleana A= si , definiti astfel si si care au urmatoarele semnificatii:

1)daca atunci pozitiile egale cu 1 din scrierea binara a lui indica punctele din multimea X de care se leaga punctul .

2)daca atunci pozitiile egale cu 1 din scrierea binara a lui indica punctele din multimea X de care se leaga punctul .

Se considera anterior precizate si se cere proiectarea unui algoritm care sa execute operatiile:

a)sa verifice daca vectorii L, C sunt corect definiti si in caz afirmativ:

b)sa precizeze legaturile intre punctele multimii X.

Pentru algoritmul proiectat sa se scrie un program corespunzator.

Caz particular

Sa se exemplifice textul temei pentru:

n=7

L=(2,1,64,32,16,8,4)

C=(16,8,4,2,1,64,32)

Descrierea algoritmului

Fie * si , fiind precizati pentru a vedea daca vectorii L si C sunt corect definiti se procedeaza astfel : cu scrierile binare ale elementelor vectorului L se genereaza matricea in care elementele liniei k reprezinta cifrele binare ale numarului natural . Cu reprezentarile binare ale elementelor vectorului C se genereaza matricea booleana in care elementele coloanei k reprezinta cifrele binare ale numarului natural . Daca atunci vectorii L, C sunt corect definiti. In acest caz, elementele multimii X pentru un i arbitrar i= se considera in care presupunem ca restul elementelor fiind 0. In acest caz, in reprezentarea sagitala a punctelor exista urmatoarele legaturi :

Procedand in mod analog pentru orice cu liniile matricei A la sfarsitul prelucrarii se vor obtine toate legaturile dintre elementele multimii A.

Caz particular

x1 x2 x3 x4 x5 x6 x7

x1 0 0 0 0 0 1 0

x2 0 0 0 0 0 0 1

x3 1 0 0 0 0 0 0

x4 0 1 0 0 0 0 0

x5 0 0 1 0 0 0 0

x6 0 0 0 1 0 0 0

x7 0 0 0 0 1 0 0

Cod sursa

#include <stdio.h>

#include <limits.h>

typedef unsigned long int element;

int main(void)

{

int n;

element l[100];

element c;

element k;

element m;

int i,j;

char ok;

/* incepem citirea ... */

printf("N=");

scanf("%d",&n);

if((n<1)||(n>100))

{

printf("Imposibil. Numarul trebuie sa fie din intervalul [%d,%d].n",1,100);

return(0);

}

for(i=0;i<n;i++)

{

printf("L[%d]=",i+1);

scanf("%uli",&l[i]);

}

/* desi aici nu am terminat practic citirea, putem trece la

faza de rezolvare si citim noi elemente doar cand avem nevoie de

ele */

ok=1;

for(i=0,k=1<<(n-1);(i<n)&&(ok);i++,k>>=1)

{

printf("C[%d]=",i+1);

scanf("%uli",&c);

for(j=0,m=1<<(n-1);j<n;j++,m>>=1)

{

/* aici avem eroare doar cand unul din numerele l[j]&k,c&m este zero iar celalaltul nonzero */

if ((((l[j]&k)!=0)||((c&m)!=0))&&

(((l[j]&k)==0)||((c&m)==0)))

{

ok=0;

printf("L/C conflict pentru L[%d] si C[%d].n", j+1,i+1);

break;

}

}

}

if(ok){

printf("Legaturile sunt:n");

for(i=0;i<n;i++){

j=0;

for(j=0;(l[i])&&(j<n);j++,l[i]>>=1){

if(l[i]&1){

printf("(%d,%d) ",i+1,n-j);

}

}

}

printf("n");

}else{

printf("L si C nu sunt corect definite!n");

}

return(0);

}

Tema 2

Pentru graful orientat , matricea tranzitiilor dintre varfuri este matricea booleana . Sa se proiecteze un algoritm care sa execute urmatoarele operatii:

a)sa genereze matricea booleana terminala pe linii asociata grafului.

b)sa genereze matricea booleana terminala pe coloane asociata grafului.

c)analizand elementele matricei booleene terminale pe linii anterior generata sa se studieze daca exista - drum hamiltonian asociat grafului si in caz afirmativ sa se precizeze ordinea de succedare a varfurilor in drum.

Pentru algoritmul proiectat sa se scrie un program corespunzator.

Caz particular: