Question

1. Fie G un graf orientat cu 30 de vârfuri în care suma gradelor interioare ale acestora este 50.
Graful poate fi format din cel mult...............vârfuri izolate.
2. Fie G un graf orientat cu 20 de arce, fără vârfuri izolate. Numărul minim de vârfuri din graf este........iar numărul maxim este.........
3. Câte grafuri orientate complete cu 10 noduri se pot forma ?

Answer 1

Ca un graf sa aiba cat mai multe varfuri izolate e necesar ca intre un numar minim de noduri sa se realizeze cat mai multe legaturi (sa fie "cat mai complet")

Suma gradelor interioare a unui graf orientat complet este egal cu n(n-1).

n(n-1) = 50

Valoarea superioara naturala : n = 8

Deci intre 8 noduri se poate realiza o suma a gradelor interioare de cel putin 50, deci restul de 42 de noduri pot fi varfuri izolate.

Raspuns 42

==================

Numarul maxim de varfuri :  21

Numarul minim de varfuri : n(n-1) = 20, deci 5 varfuri.

=================

Minim n(n-1)/2 si maxim n(n-1)

Deci minim 45 si maxim 90