Grafuri neorientate - noțiuni introductive

Grafuri neorientate - noțiuni introductive

​

Graf neorientat

= pereche ordonată G=(X,U) - X mulțimea nodurilor, U - mulțimea muchiilor

În imagine:

X={1, 2. 3, 4, 5, 6, 7,8,9}

muchie - pereche neordonată de noduri

U={[1,2], [1,4], [1,5], [2,3] ,....}

Multiple Select

U={[1,2], [1,4], [1,5], [2,3], [1,6], [6,7], ,....}

• [6,8]

• [4,6]

• [2,3]

• [5,1]

• [8,7]

Terminologie (1)

• nodurile între care există o muchie se numesc adiacente. Ex: 2 și 3 sunt adiacente pt că [2,3]∈U

• muchiile cu o extremitate comună = incidente Ex[1,2] și [2,3] incidente pt că au nodul 2 comun

• un nod care este extremitate a unei muchii este incident cu aceasta. Ex: 1 incident cu [1,2]

Multiple Choice

Nodul 1 este adicent cu

• nodurile 2, 3, 4, 5, 6, 7, 8

• nodurile 2, 6, 4, 5

• muchia [1,3]

Terminologie

• numărul de noduri = |X|=ordinul grafului. Se notează cu n.

• numărul de muchii = |U| se notează cu m

• m=0 => Graf nul

Fill in the Blank

n= ?

Fill in the Blank

m= ?

Fill in the Blank

Număr de noduri: n=2

Număr de muchii: 0 ≤ m ≤ ?

Fill in the Blank

n=3

0 ≤ m ≤ ?

Multiple Choice

Având în vedere faptul că orice muchie este o mulțime de două noduri din cele n:

0 ≤ m ≤ ?

• n²

• C²_n

• 2ⁿ

Terminologie (3)

Fill in the Blank

În K₆

_m=?

Gradul unui nod (4)

• =numărul de noduri cu care este adiacent nodul respectiv

• =numărul de muchii cu care este incident nodul respectiv

• Notație d(x)

• Ex: d(1) = 4

Fill in the Blank

d(5)=?

Fill in the Blank

d( ? )=0

Fill in the Blank

d( ? )=1

Terminologie (5)

• nod izolat= nod cu grad 0

• Ex: d(9) = 0 => 9 este nod izolat

• nod terminal = nod cu grad 1

• Ex: d(3) =1 => 1 este nod terminal

Multiple Choice

Într-un graf nul, toate nodurile sunt

• terminale

• nule

• izolate

Multiple Choice

 $0\le d\left(x\right)\le$  ? , în orice  graf neorientat de ordin n,

• n-1

• n

Relația între grade și numărul de muchii

Open Ended

Dacă ne gândim la toți oamenii de pe Pământ, putem afirma cu certitudine că numărul de pesoane care au dat mâna cu un număr impar de persoane este...