Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri, etichetate de la `1` la `n` și un număr natural `k`. Din acest graf se elimină toate muchiile care au ambele extremități în vârfuri de grad mai mare sau egal cu `k`. Să se afișeze matricea de adiacență a grafului parțial obținut. = Date de intrare = Fişierul de intrare `graf_partial_5IN.txt` conţine pe prima linie numărul...

2023-12-12T23:21:32Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code> și un număr natural <code>k</code>. Din acest graf se elimină toate muchiile care au ambele extremități în vârfuri de grad mai mare sau egal cu <code>k</code>. Să se afișeze matricea de adiacență a grafului parțial obținut. = Date de intrare = Fişierul de intrare <code>graf_partial_5IN.txt</code> conţine pe prima linie numărul...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code> și un număr natural <code>k</code>. Din acest graf se elimină toate muchiile care au ambele extremități în vârfuri de grad mai mare sau egal cu <code>k</code>. Să se afișeze matricea de adiacență a grafului parțial obținut.

= Date de intrare =
Fişierul de intrare <code>graf_partial_5IN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului și numărul <code>k</code>. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>graf_partial_5OUT.txt</code> va conţine 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 =

* <code>1 < k < n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare

= Exemplul 1 =
<code>graf_partial_5IN.txt</code>
6 3
1 4
2 5
2 4
2 1
4 5
3 2
4 3
2 6
3 6
<code>graf_partial_5OUT.txt</code>
0 1 0 1 0 0
1 0 0 0 1 1
0 0 0 0 0 1
1 0 0 0 1 0
0 1 0 1 0 0
0 1 1 0 0 0

= Explicație =
Se elimină muchiile <code>(2 3)</code>, <code>(4 3)</code>, <code>(2 4)</code> deoarece vârfurile <code>2</code>, <code>3</code> și <code>4</code> au gradul mai mare sau egal cu <code>3</code>.

== Exemplul 2 ==
<code>graf_partial_5IN.txt</code>
1000 1000
<code>graf_partial_5OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_input(cale_fisier):
with open(cale_fisier, 'r') as fisier:
n, k = map(int, fisier.readline().split())
muchii = [tuple(map(int, linie.split())) for linie in fisier]
return n, k, muchii

def verifica_restrictii(n, k, muchii):
if not (1 < k < n <= 100):
return False
for muchie in muchii:
if not (1 <= muchie[0] <= n and 1 <= muchie[1] <= n):
return False
return True

def construieste_matrice_adiacenta(n, muchii):
matrice = [[0] * n for _ in range(n)]
for muchie in muchii:
matrice[muchie[0] - 1][muchie[1] - 1] = 1
matrice[muchie[1] - 1][muchie[0] - 1] = 1
return matrice

def elimina_muchii_grad_inalt(matrice, k):
grade = [sum(rand) for rand in matrice]
for i in range(len(matrice)):
for j in range(len(matrice[i])):
if grade[i] >= k and grade[j] >= k:
matrice[i][j] = matrice[j][i] = 0
return matrice

def scrie_output(cale_fisier, matrice):
with open(cale_fisier, 'w') as fisier:
for rand in matrice:
fisier.write(' '.join(map(str, rand)) + '\n')

if __name__ == "__main__":
fisier_input = "graf_partial_5IN.txt"
fisier_output = "graf_partial_5OUT.txt"

n, k, muchii = citeste_input(fisier_input)

if not verifica_restrictii(n, k, muchii):
with open(fisier_output, 'w') as fisier:
fisier.write("Datele nu corespund restrictiilor impuse")
else:
matrice_adiacenta = construieste_matrice_adiacenta(n, muchii)
matrice_modificata = elimina_muchii_grad_inalt(matrice_adiacenta, k)
scrie_output(fisier_output, matrice_modificata)

</syntaxhighlight>

4072 - Graf Partial 5 - Revision history