~ info project ~

Mai 5, 2010

Graf parţial şi subgraf

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:40 pm
Tags: , , ,

Fie graful G = (X,U). Un graf parţial al lui G, este un graf G1= (X,V), cu . Altfel spus, un graf parţial G1 al lui G, este chiar G, sau se obţine din G păstrând toate vârfurile şi suprimând nişte muchii.

Fie graful G = (X,U). Un graf parţial al lui G, este un graf G1= (Y,T), unde şi , iar T va conţine numai muchiile care au ambele extremităţi în Y. Altfel spus, un graf parţial G1 al lui G, se obţine din G eliminând nişte vârfuri şi păstrând doar acele muchii care au ambele extremităţi în mulţimea vârfurilor rămase.

Exemplu:

Se consideră graful G = (X,U) din figura 2, în care X = {1,2,3,4,5,6} şi U={u1, u2, u3, u4, u5, u6, u7}.

–         Construim graful parţial G1 = (X,V), unde X = {1,2,3,4,5,6} şi V = { u2, u3, u4, u6, u7} (figura 3) din graful G au fost eliminate arcele u1 şi u5.

–         Construim subgraful G2 = (Y,T), unde Y = {3,4,5,6} şi T = {u4, u5, u6, u7} (figura 4) din graful G au fost eliminate nodurile 1 şi 2 precum şi arcele u1, u2 şi u3 care au o extremitate în afara mulţimii nodurilor rămase.

Lasă un comentariu »

Niciun comentariu până acum.

RSS feed for comments on this post. TrackBack URI

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

Creează un sit web gratuit sau un blog la WordPress.com.

%d blogeri au apreciat asta: