AntalKrisztian: Pagină nouă: == Cerinţa == Se dă lista muchiilor unui graf neorientat cu '''n''' vârfuri, etichetate de la '''1''' la '''n'''. Din acest graf se elimină toate muchiile cu o extremitate într-un vârf de grad maxim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut. == Date de intrare == Fişierul de intrare '''graf_partial_2in.txt''' conţine pe prima linie numărul '''n''', reprezentând numărul de vârfuri ale gra...

2023-12-29T18:31:43Z

Pagină nouă: == Cerinţa == Se dă lista muchiilor unui graf neorientat cu '''n''' vârfuri, etichetate de la '''1''' la '''n'''. Din acest graf se elimină toate muchiile cu o extremitate într-un vârf de grad maxim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut. == Date de intrare == Fişierul de intrare '''graf_partial_2in.txt''' conţine pe prima linie numărul '''n''', reprezentând numărul de vârfuri ale gra...

New page

== Cerinţa ==
Se dă lista muchiilor unui graf neorientat cu '''n''' vârfuri, etichetate de la '''1''' la '''n'''. Din acest graf se elimină toate muchiile cu o extremitate într-un vârf de grad maxim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut.
== Date de intrare ==
Fişierul de intrare '''graf_partial_2in.txt''' conţine pe prima linie numărul '''n''', reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere '''i j''', cu semnificația că există muchie între '''i''' și '''j'''.
== Date de ieşire ==
Fişierul de ieşire '''graf_partial_2out.txt''' va conţine pe prime linie numărul de muchii eliminate, iar pe următoarele linii matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.
== Restricții și precizări ==
* '''1 &les; n &les; 100'''
* '''1 &les; i , j &les; n'''
* muchiile se pot repeta în fișierul de intrare
== Exemplul 1 ==
; graf_partial_2in.txt
6
1 2
6 2
2 3
4 3
5 3
4 5
3 6
6 4
; graf_partial_2out.txt
Datele de intrare corespund restrictiilor impuse.
4
0 1 0 0 0 0
1 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 0
0 1 0 1 0 0
<br>
== Explicație ==
Se elimină muchiile '''(2 3), (4 3), (5 3), (3 6)'''.
== Exemplul 2 ==
; graf_partial_2in.txt
jgirjiurmgrog
; graf_partial_2out.txt
Datele de intrare nu corespund restrictiilor impuse.
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
# Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat
def validare(n_validare, muchii_validare):
# Verificăm dacă n este în intervalul 1-100
if n_validare < 1 or n_validare > 100:
raise ValueError # Ridicăm o eroare dacă n nu este în intervalul 1-100
for muchie_validare in muchii_validare: # Parcurgem lista de muchii
# Verificăm dacă valoarea absolută a fiecărui vârf este în intervalul 1-n
if (abs(muchie_validare[0]) < 1 or abs(muchie_validare[0]) > n_validare
or abs(muchie_validare[1]) < 1 or abs(muchie_validare[1]) > n_validare):
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

# Funcția elimina_muchii elimină muchiile cu o extremitate într-un vârf de grad maxim
def elimina_muchii(n_elimina, muchii_elimina):
# Calculăm gradele vârfurilor
grade = [0] * (n_elimina + 1)
for muchie_eliminare in muchii_elimina:
grade[muchie_eliminare[0]] += 1
grade[muchie_eliminare[1]] += 1
# Determinăm gradul maxim
grad_max = max(grade)
# Eliminăm muchiile cu o extremitate într-un vârf de grad maxim
muchii_eliminate_ = 0
muchii_noi_creat = []
for muchie_eliminare in muchii_elimina:
if grade[muchie_eliminare[0]] == grad_max or grade[muchie_eliminare[1]] == grad_max:
muchii_eliminate_ += 1
else:
muchii_noi_creat.append(muchie_eliminare)
return muchii_eliminate_, muchii_noi_creat

if __name__ == '__main__':
file_in = open("graf_partial_2in.txt", "r")
file_out = open("graf_partial_2out.txt", "w")

try:
# Citim numărul de vârfuri
n_main = int(file_in.readline())
# Citim muchiile
muchii_main = [list(map(int, linie.split())) for linie in file_in.readlines()]
# Validăm datele de intrare
validare(n_main, muchii_main)
# Eliminăm muchiile cu o extremitate într-un vârf de grad maxim
muchii_eliminate, muchii_noi = elimina_muchii(n_main, muchii_main)
# Scriem numărul de muchii eliminate în fișierul de ieșire
file_out.write(str(muchii_eliminate) + '\n')
# Scriem matricea de adiacență a grafului parțial obținut în fișierul de ieșire
matrice_adiacenta = [[0] * n_main for _ in range(n_main)]
for muchie in muchii_noi:
matrice_adiacenta[muchie[0]-1][muchie[1]-1] = 1
matrice_adiacenta[muchie[1]-1][muchie[0]-1] = 1
for linie in matrice_adiacenta:
file_out.write(' '.join(map(str, linie)) + '\n')

# Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
# Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

0422 - Graf Partial 2 - Revision history