Rezolvare sesiunea speciala BAC 2018 Informatica (MI) – Subiectul al III-lea problema 3
Mai jos puteti gasi enuntul si rezolvarea problemei 3 de la subiectul al III-lea de la sesiunea speciala a examenului de bacalaureat la informatica (mate-info) din anul 2018.
Rezolvare:
Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂
II.2. Numărul de noduri ale unui graf neorientat fără cicluri, cu 26 de muchii și 12 componente conexe este:
Care ar explicația pentru răspunsul 38?
Salut. Pentru inceput trebuie sa ne gandim ce ne spune faptul ca graful nu are cicluri. Daca nu are cicluri, inseamna ca fiecare muchie adaugata la graf, pune un nod la graf. Lucru explicabil prin faptul ca daca muchia leaga 2 noduri deja existente, aceasta ar face parte dintr-un ciclu, dar graful nostru nu are cicluri. Deci pornim de la un nod. Adaugam o muchie (din cele 26) si acum avem 2 noduri. Mai punem o muchie, si avem 3 noduri (2 muchii – 3 noduri). Inca o muchie, inca un nod (3 muchii – 4 noduri). Continuam dupa acelasi principiu si avem 26 muchii si 27 de noduri. Dar acum avem doar o singura componenta conexa (toate muchiile le-am adaugat la aceeasi componenta). Deci mai avem nevoie de 11 componente conexe, fara muchii. Deci inca 11 noduri. 27 (prima componenta) + 11 (celelalte componente) = 38 de noduri. Sper ca am explicat ok. Zi faina si spor la lucru.