Exerciții 1366

Se consideră un arbore cu 8 noduri și muchiile [1,2], [2,3], [3,6], [4,3], [5,7], [7,2],[8,2]. Înălțimea arborelui este egală cu lungimea celui mai lung lanț elementar care unește rădăcina de o frunză. Arborele dat are înălțime minimă dacă se va alege ca rădăcină nodul:

Șirul de valori care poate fi vectorul de tați al unui arbore cu 8 noduri este:

Un graf orientat tare conex are șirul gradelor externe ale vârfurilor sale (3,1,1,1). Graful nu are arce cu extremitățile identice (bucle). O variantă care poate reprezenta șirul gradelor interne ale vârfurilor grafului este:

Precizați care este numărul de grafuri orientate distincte formate din 3 noduri și 4 arce. Două grafuri sunt distincte dacă au matricea de adiacență diferită.

Un graf orientat se numește turneu, dacă între oricare două vârfuri i şi j, i<j, există un singur arc. Precizați numărul grafurilor turneu cu n noduri (n număr natural cunoscut)

Fie T un arbore cu rădăcină având 2025 de noduri numerotate 1, 2, ..., 2025, având proprietatea că vectorul de tați al lui T este (0, 1, 1, 2, 2, 3, 3, 4, 4, … , 1011, 1011, 1012, 1012). Câți ascendenți are nodul 2024 din T?

—

Vă rog să scrieți enunțul în cuvinte. Imaginile nu se afișează corect în anumite condiții, nu se pot realiza căutări, etc. Mulțumesc!

Considerăm următoarele cinci afirmații pentru un graf neorientat G:

• G este conex
• Numărul de componente conexe ale lui G este mai mare sau egal cu 1012
• G are cel puțin un nod de grad 0
• G are cel puțin un nod de grad 1
• G are cel puțin un nod de grad mai mare strict decât 1

Câte dintre cele 5 afirmații sunt adevărate pentru orice graf neorientat G având 2023 noduri cu proprietatea că matricea sa de adiacență are exact 2022 de valori egale cu 1?

Un graf este bipartit dacă nodurile lui pot fi împărțite în două submulțimi disjuncte, astfel încât fiecare muchie are o extremitate în prima submulțime și cealaltă în a doua submulțime. Fie G un graf neorientat, bipartit, cu 10 noduri. Numărul maxim de muchii pe care poate să le aibă graful G este?

Un arbore cu 11 noduri, numerotate de la 1 la 11, este reprezentat prin vectorul de „tați” (4,3,7,6,7,8,6,0,7,7,7). Indicați numărul maxim de descendenți direcți (“fii”) ai unui nod.