Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Reprezentarea grafurilor - matricea de adiacenta

Reprezentarea grafurilor prin matricea de adiacenţă – probleme propuse

1. Se consideră fişierul graf.in care are pe prima linie două numere naturale n şi m, reprezentând numărul de noduri respectiv numărul de muchii dintr-un graf. Pe următoarele m linii se găsesc câte două numere i şi j cu semnificaţia: există muchia (i, j) în graf. Valorile i şi j sunt între 1 şi n, deoarece nodurile sunt numerotate de la 1 la n.
a) Să se scrie o funcţie care citeşte din fişier datele şi construieşte matricea de adiacenţă;
b) Să se scrie o funcţie care primeşte ca parametru o matrice de dimensiuni n x n şi care returnează 1 dacă matricea este simetrică faţă de prima diagonală sau 0 în caz contrar;
c) Să se scrie o funcţie care primeşte ca parametru un număr natural i şi returnează gradul nodului i;
d) Să se scrie o funcţie care afişează nodurile izolate, nodurile terminale şi nodurile de grad n-1 (dacă există!);
e) Să se scrie o funcţie care primeşte ca parametru un întreg i şi afişează adiacenţii nodului i;
f) Să se scrie o funcţie care primeşte ca parametri două matrice a şi b de dimensiuni n x n reprezentând două matrice de adiacenţă şi returnează 1 dacă graful corespunzător matricei a este graf parţial al grafului reprezentat de matricea b;
g) Să se scrie o funcţie care returnează 1 dacă un graf este complet şi 0 în caz contrar.

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =