0 ratings 0% found this document useful (0 votes) 33 views 11 pages Graph Notes
The document discusses graph theory concepts including vertices, edges, directed and undirected graphs, and their representations such as adjacency matrices and linked lists. It also covers traversal algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS), along with their applications in various fields. Additionally, it mentions the importance of these algorithms in finding paths, detecting cycles, and producing minimum spanning trees.
AI-enhanced title and description
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here .
Available Formats
Download as PDF or read online on Scribd
Go to previous items Go to next items
Save graph notes For Later Orban2n Ton,
brvaeh Teaminolog sso sm
@ vertex: A verter 4 % Bynony rm for *
node: A Vertex B Dug verented bow a Kivcle.
Ry!
4 © 3 © Wee B22 oe,
Vedices
® Edge: An anc or a Line jong dune
Verkices py Ui and V ig Called an edge
Eq;
Si o—-4
a) Undi rected edge : No cireclvon boo 2 veakces
2) ee
* Denoted an ordaed Poor ORS)
*(2) 1, Beme % (2,1) in am undiverdd che.
b) Divecha tyes a divection exists blur 2
Ve aki ces. pias
Sd Eipege Oy — 3)
* Denoted Ei He ivectod Pedy Be Viane
\ \~ Catted tail oy a
ead 0] ME Udy Hence ia!
on ony U2) ig rob Banc
® Creagh — Formally, a qragh BS uw ayn ed. C8
| o patsy of two ads N and E, dtncked by
, G= 8) Mesias 22
Be} <1,67 1,27, 22,39,
)
at 37) S573 7, <5.6>,
Kore D3
a ® \wie 6 HP no. ef vediees te qe
a:
‘ ala Ak cis ool ha
® Divected Greghs A geek G= (V, ED fe worth
edge jg directed 1S Eo Siaare Atco ced YES
pam Called Os dg raeren™
F be cco), COs Ree jas
£24 6027, 42,47, <8),
“ iy, 37, 273
Undivected Gack: A qreeb tnatetped Beane
Wy undivectect ts tallad an Urdiredel seh. i
ate 8 253%
aes Goad, 2 3,038),
(2,3), 3 :
ke be a Comelebhe
Mes edge’ bio very ‘pair af ee ee eee
welt: For a lomAake 9101
¥ | wike NM VENthlees He,
be m(n=1) /2 edger
® poms
*& pal 6 denoted sk ny feqyerca OF
vertices and }kare les an edge from
one verter to neck verte,
Y A) The pads fom Nok Viele 1,
denoted 7,2 3,4
tO (on ales be tdriffen a2:
3?) sb2ys) ¢ sy
The poh fern Vet 1 te z
nes Ny Ny iB CO
Or ates Nee Wathen as:
MHD <>, C2,
@) Sime Pa? p single etal cee eae okey
vowdh all vertices except
and task ore distinct,
fa
Peaei bly jee fives
p 4 Tr He qieeh, Wa path ae
hg = cimple hg
nods Ta Mee Bequence Me seks ot.
lovvesms only One, ee
© Lene eee te Pal t ne. 2) te ye cln
quits Wer et, ete
Fy! 4) 5. ee 2 pazcedted ) we Rach be teaneckedh UY and Prly
4 yore eniats pak dblw erey Par of yahoos
a SC
(3) 4
ey
Pydirncted ved! A me
Basten necked ’ sf ah: 5
eee Rak wnno a
in Sah
a Pk)
®
3
4 FG wagh Rep rAckentations $ —
| Thesia aro tO methods!
a Prdjocency Mataix
Linked List
oO
Brita. .h zai, fe
ablenst one Verte
cenchsd from other F
avs
Pete G2 (ve) be A qroph. teh WV ue He ney
Veakices ta Ouegte & . The Adjacency, matyix A
Ba qm A is dyined on:
is
f Barts ‘ 4 thee 4 on fom verter UB ZG,
ata: | aos
O Mme % no edge from vet Tj. gs
ute on’. “‘rocos
a boolean aqiare matrix
t's and bls.
tolumns » with entries
gg fig 70s eka
© diceded qragh »
gD
bes?
© Undivected qraeck
My
w
. fidadiaia ts
sf x fete er ae TAN
@ (3) ate
OF wit bo
Shape bc
b) Adjoceney Linked Lists-
ye heen Cre (y, E) be a gyreh - a adjacency
Méaked Atay is an onrsy ef ‘n! Hiatead
iste whee YN & He Noe | vertices
Bn geek ©:
Eack Letation & he ONS. GS & Varker
ange VF : :
x for eoch vertex UEV, a Baked a.
of out Wo vertices adjecent be UU Cveated
and stored fa ate)
Frome les Coy) o bial] favolved Or
ae cork
problem 4
on he OF eels ee maf aaehn eS Coa BR) NPS tankeg
a anjOcanety malay § Or adj actncry Linked lif,
he ovfpocen 4 molyh Conslata 9 weight ( Coat) Can,
ale be dottid om Cork Adfacency Matby tr.
The Adv Liaked: Lists wily coats tan be
fated os Coat fatioceney U Unde ik
| Dyos Lek & = every ie a graph , Wie 1 no,
6 Neaticca, The Cost od’ moder ef
Arnel ta Yormatly deyined 8}
ALi) Ly) + + af When 14 a weght astredted from
Vertex to j,
Hone ede fom ©
| Fangles Using Cost Adjoceney mation onc Cost Ay Lid
a) Fea directed seh : ee
Ee 20 | m 1
aA
nee 15 | 00
2 iets ss olso| * >\z3e)_]
3B) {254 BW {oO
345 analy
Nie eo
») Fon re N wer Adj. Liat
OVO folvlaa| teas 2a4/
Ws a8 aa t pel bea ps7
2) eet - fel ST 7
we Mra THEA
Cont Waly tvnked Lt nay
ps eae ate Len; tar)
der (f= oy f Reyer Lab. Proprom “ihe
APeLicatios Of RES and Des ¢-
BES © © To frd Chose pore
to anotta Vertex In an tenwerplded 9 lap,
@ To fred Ys qraek Covdains Cycler .
& Tn Peer Reer nehvorke ,
() Soca network, welesiier.
@' GPs nowig att on agalem .
A vertex
DES* © Produces Minimum BPonring tree and
alk shsrteot Pal tree.
@ Te dcotect cycles
© Copolog Nak Sorting
() To find — Comhested Grates
