Scribd
Upload
52 views75 pages

Graph Theory

The document provides an overview of graph theory, defining key concepts such as vertices, edges, loops, and parallel edges. It explains different types of graphs, including directed and undirected graphs, weighted graphs, and finite versus infinite graphs. Additionally, it touches on properties such as adjacency, degree of vertices, and the handshaking lemma.

Uploaded by

Joy Sengupta
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
52 views75 pages

Graph Theory

The document provides an overview of graph theory, defining key concepts such as vertices, edges, loops, and parallel edges. It explains different types of graphs, including directed and undirected graphs, weighted graphs, and finite versus infinite graphs. Additionally, it touches on properties such as adjacency, degree of vertices, and the handshaking lemma.

Uploaded by

Joy Sengupta
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
You are on page 1/ 75
Dnrk ave Graph ‘Thoory A graph is simply a collection of, points, called * vortices? [and a __coljecHon!of ines, called + Edges! each of nieh ae either & t - points or a single oir fa itso) KS fa m ~_| 40 giaph G is an ordered jolt CVs E) yorvcos & E is the set oF al pes - +o A 24. | Graph _aepresentin ‘| taeighted Graph + “det G be a_giaph with verter Se V & edge sel 6. op each alge 0 cach verte or bol) are assoc Fiphh some positive ead numbers then he gtaph js coed a _Wwoighted @idph . _ a | pa “system of _ pipelines ae F the! weights assitned indicalo the gmount oF cone — commodif} _transkgeared _timough the pipe fa “weighted | graph.” i te . —— _ ee Aig @_shotls a weighted graph where weights assigned Jo each edgo. — : | ict 4 x 2 @ a ft wv > = ota | ae = i 4 x a fig. os @ Finite ond ‘Infinite Qaphs A giaph with finite number of vertlces as well as _finike number of, edges ts cated as_a_ Finite Graphs 5 | other@ise, iF is on infinite grap | @oph @ in Fig. 65 @ jsa_ Finite graph. | [dab Aabetled Guaphs R_giaph @= CWE) is called a labeled graph if its_edges ne labeled with some namo ov data- _ For et 7 a ~— graph in fg 6.5 © fsa labeled graph. Here G= 94u Vo.,%3,Nu Fs 12102, Ca, MH, e5 FY whore V= 4 Wva, Va,v4 y & E= } 0,0 03, 24, Os} oa ee | Some i ao important & Usokul graphs SSS a} Graphs ‘or Digiaghs - A directed ataph or a _ fi Aqraph P isan ordered Qi..a) Whore \ ts a Non- emppy Seb of — elomonts calee| _ Nertices & A is tho sok of orderog palr of olements | atid direct ans. — ‘s l Ie incched Edges OY 5 ; iq shat tf tho eath ef af I parerrcanense | | Tn other words, “we can sa | Aho_gtaph @ has « diredion then tho _gtaph is J cowed dinecte} sph s1_digrayh - Me ok I Fig os have diftaph D= (v.A).in which the vortoa sep [an Aq we [ova 03M, Vasa Vy & the directed edge sera 7 | A =o, Cr, 09, O05, C604} “ai ho eddes ave. gen by y= fw N3y, = {vo y | es J v23y Py awty es = Avi .V2) $ L [eps Oa). [ | a [Multiple ans + Ine Vorces Vy & V2 are, joined by mare [ “than one ore With the Same! diredion | | | mar l [Sun ames are Cajled a3 Wulliple ons. mhe 6 06 4e% are not mull pls, “976 boacanad dhelr ditecions are gtfforent though _ “Shofr end Vortices are Same: || an qhove' fig are @ iS 4 sel Soop - ano sAlf i ne on, Joop | tor Aho ww_dighayh_ is dof, ied, exact nde | f Pndivected Graphs Mary lS +7, graph contalning unordered pal OF vertices is called as onshacte graph - | ran an undivoced graph, paly of verties CAs 8) dnd (B.A) Froprsent the same edge, TT examples - mn = O) 7¥ | Simple digraphs - Digraphs oitnout loops & multiple arcs = ore known as simple _aigraplas. + _ il nud: Wall Graph 3 Gp the. ego sof of any_giaph with n vorkeg z [ is on emph) Sor, tod the graph is know Jos Null @aph or edgaloss graph. t - | zis denoted by No. i | Following are "tha examples of null graph on 9 Vela (2 y Sveeticas sospectivel . i a —— oo = | Adjacont Nertfeos = ‘Two Wertices | Vi&\ of a grogh@ Gre Said to bo Adjacent +0 Qady gti LHC they ore te end vortices op sha same edgn « Gn oper words , ; | jE oo vortices ave joined diresty by a least ona | edge Men there ore Yortices aval called Adjacent ei — = is Tn_fig. Niond Yo one adjacent Vertes bur V4 re ee For imeidenco ee Ie tho yortem’ Vi |g tho ond. Vortex of an edge “i= CViyj)_then the eye elf is_safd to be inedont on Vi. q p E Oo Similanty, efj_is sald 40 be inchdent onVyr. t Ky SaaS SS [gn above ait. 2 15 incident onV) &Vo Adjacent edges gs Tio non- porallel edgos ave sar4_to be adjacent ip hoy ove _fneident ono We \\\\\ common Vorkex. [ for eq. @ de aro adjacent. Similarly, ee & ew aieY dl6o adjacent edges 7 | Degree oF a Noster - The number of, edqas_ineident ona Noiter Vi with sd ace counted twice, 1s callod “tho, — of the Vorte tt is. donoted by d Wj) - || Vie} | | | T the folloWing fq. dy) =3 / dws) = 3, d(Vg)= 4 dy) = 3 ds) = 4 q(Ve) = O- 3 “= Solated Verler <2 pendant Vorb ree a | A Nerlow with degree vero is cured 45 a0 isqated Verte g — —— 01 A_vettes_havingy no incident edge ss.an ‘solated very —__ [an _ fig. Vor ies’ 39-3. Handshatingp Jomma_ — | Consider a Graph @ with e_ me. alder & number of “vertices.” Since “each edge contrib swW0 degrees “the [sum b tho dogaos Cof au vortices In Gis “bolce Bw number of odges in G. Ie i 0 l divi) = 2e i ne | This fs called yandshating domna - ® & Thoorem : Tho number oF vorticos of odd dogereo ina | graph is always often. yatook + i f Jot G be a graph with o edges &1n number of | Vertices - __Ss : | Thon by Hand shaking Jomma, _[ tn es _ ee = diyj) =9e = even number: s “jet 3 SNow, the total dogreo of all the Vortites cay kl ie z r =, | AA “ We os the sum oh degreas oF even degree verlices & od “pyre. vertices - ses S_= Oj) +2 We = = dui) — [— ~ Ceven degree verices) + a degree Vortices) | [> dy) +5 d0y) =2e= a0 even umber (Coven degree Verlicos) | | Bur “the sur of degrees oF _ even deyree vores wd dluvays bee dij) is even 9¢ & 2@ is always an_even number. qhoropore, the sum of degaeas op odd degree voxkices cheuld bo 0 even | > dW) = _an_e¥en number. odd degree vorlies. This ghows tha the gum of tho degrees of odd Vertices is an even number & which is possi bw on When Bu numbor ‘) odd degtes Vertis is ‘even Some i ora S_Osoful_ graphs graphs Direct} Graphs or Digraphs - A directed graph ot digraph P is _ao ordored Ov. A) Whore \) is a@ Non- emp Ser of — elomonts cabled | Vertes & A is the sot of ordered _pafr_of alements | cated dineced edges_ov “ans a a Hor ds, we can sa shart o eu | Jn oor wor see Ane graph G “has a _dfrechon thon tho _giaph is 8 ~| cated ineche} _guaph os fies T fig wo have di4raph va 0 3M, Vo,¥a. Wy yp & the directed edge seh A= Jor, er, 09, 0H, 25, C604} @ho edges are. given by @ = (Nay, &= {vo.v9) | @= 4 Vo,v3y Coy a Yaw er = Bvi.V2) | ey. iq o8- ea De (vA) IN which the vorton sek | eye CW2,My). auiliple aves: (no Vortices Vy & Vo. ore joined a more — =than one ate with the same! diredin Such ares ave Called ot NMulliple ams OS mhe as 6 404 are mot mullite a7 beacaned thelr same- Samo way an above fig are & is a selF Joop : d{recHon3 are dy fforent hough shofr end oa qo self Joop tor Aho dignaysh_ is dof, trte4 oust ind — Useemate ’ >) Bate — =} (yo ¢ Undivected Graphs: — R Graph containing — pay Of vertices is culled as “undivected graph Y Tp an undiveced graph pal of vertices CAs) and (BA) | crappros ent tho_ same edge. examples = we Se ie 74 _—t classmate Ox lo Vgraphs. = Diguaphs colthout “oops & multiple ass are KNOWN as simple digrophs ~ het uw be any Vertex oF the didtaph p=(y, 5) Anore tor Jin p is sald to Be_tnddenk _ tne tho Vertoe uw if it is of the Form CVv,u) For Some. € \. Similarly, ta'_\s_savd to be incident out oF te Yorker w te ik is of, the form (u,v) for some ve \V- 4. | er is indent into the vorjor Vo d& Incident oul of tho Vevter Vy in Bq B.8- & - Mndegree & oubdeg ree Tho indearoe of a Vortex w of digraph D ts derined as the number of ares which ore incident into Ww & is denolod | by ? “Guy. or ‘No.of edges coming jo the verter uw { Sina, the oukdegreo of a Vere u is defined as the | | number! igh ons ars which_ave ineidenr ore _& “ts denofed — by aud, or No- oF edgos “gam 0 out jyom Verte W. | - ae — yo oe Za 36 Yo, ) ieee {anda neo [outdegres f Mt 3 3 s ey Nou ay 2 -t Va a7 at v Va ez. 4 ire but its_anderl . Hore Dy tsa_Si imple [ks nota Simple raph. bela Cla Graph 2 Tr +ho_odyo sot of an raph —} with _n Vertieg is on emphy_ sor, thon’ the yaph is knoup| as SNalj_@aph or adgoless graph. Iris denoted by No. | Fotowing are | the & yy “vertices mrospestivelt - eramples oF null graph on 8 Verkees)- o ° ° _ oO ° oO ° N, Ny a poo | Complete Giaph - Let @ boo Simplo graph on _n Vorlies | al gp tho dogwoo of ench vorlee ts (ny, | [-Ahen the graph G Is called o compa graph. dendted 4 [ ko |More _ generally, IF aiory pay of vortices $s adjacent rh at [simple gtoph , thon tho graph 45 said ko be || Compete _qraph_. : ; Complete grap on m- Vertes is denoled by Xo a Xo_ TI a — ; okt we ; oN - ee s | [duo =) d 7 [tvs = as be [No.of VerteR= 2 “Ma-of Vertex =3 I diwiy = dtv2) =d(Va) =2- i classmate, y I too Complete grap kn, mo. oh, edges ore _[ (n-1) tes Regular Groph__: TF the “degree op each verve is some Say ‘a ip any graph G , then the raph G_is sold to be a “aggalir giaph of, degree or. ia \_\ MS \_\ | Aegulat graph oF degree cr tS also called a8 = crogpulor ‘ gay app nf Teguler graph of degree 2 Is also called 9 = cregpular graph, oh potas graph shown in fig @ isa wegular graph oF & oVa __d(vp) Dol I Tinto Hoo non- empky disjoint _Gubsets_% & Yin | such way that ea adgo of G has one _end in ¥ } ano end In _Y then G is tallest bipartite, | | 10 & ny = & Bax ot 2 oe , a_O | Qe ® LAK a | A) ee | 41213) : k= 7 105304% Not % WS % | il . oe [7 = i4osist + [| _ ____+ ~ | Complete Bipartite Graph _: TF em verte in X 15 joined evory V op Y_-then We col te a complet wd. biportite 9 ~__ | Denoted i Km where m €n ore number oF ~_ | vevties in) x & respon A= 2b3} qo eet eer t+ | ¥ = Yout 6} 1) [-meo j med | Koo | | S 7 [X= Qn36FF ly = 224,58} [ mey Ney : ~ ! Kany GQ —O DO - 4 ko,3 x= Wn2d Sy ys 9 3.45 m= 2 N=3 “lien Szabat RR Ks ) ve Vysied : _ m3 ,n=3 | Gxamples of Bipartrte Graplo Se t SS oe ws Ve : : i We Au ViWi} Ve ad? No = {Un ,Vo) Wey Vo = {biuret weighted Gogh: K unighted_giaph isa grap s—_AN_edge may “represent _o highway tink between 00 | example: edges “ote ass goed gore Yalan, Uleight will denote “the distance be? 100 ~comnocted cities - pleight of an edge is alse called as cost: | ZS I we x Ss 3 Ne 9, A OANS : - ZN, ‘ NG lo Ny Suppose we have & giaph Ge VET. ° ; Gubgraphs _: per? : = 8 A graph Give!) is sald +2 bea Sulegraph of Gif E' ts a Subset of 'E and vi is a_subseh ToRv._ Such that edges’ in €' ave Incident omg with verties | jo Ve Note. ‘VE contains i the erg paints of edges met | Jhe graph G riself & Sw) gvaph obtained by doleling al) 5 of any graph G-_ the edges of, -4 are Subgia ph (o “gubuapb £04) ©_Bull Gaph (.Subgrapb 2) @ (Gubgraph 3) FS : —— ra I 6 subgraph 4 @_Subgraph 5 : + ro pert OS : (| _ Gach graph is a a. subdwoph of ftselF ©) A single Votes of graph ts also a subgraph oF | graph G. _ : (s)| A single edge along with end vortices is dlso a Subgyaph» Hf g tA subgraph of a Graph G is also a subgraph OF Gs | 5) Spanning. Subsraph A subgraph 95 said 4o he — (example - Graph _@' is a Spanning “subgraph oF Graph G oo ; Graph - Giaph @! 4 © . Cdge disjoint subgraphs + Two _subgiaphs Gr & Ga. of ine ; Spannin al! vortices oF Ge ee ving _subaraph JF ft covtuins __— gupb G ave said to be edge disjoint gubgiophs of a Graph G te there is No eage common between Gt & Go. » Fwo sikqaphs Gi d Go of the Noer disjoint Subgraphs _: qvapb G ave said to be Vertes, disjoint subgraphs ’ of the graph if theve is no Verte common betwee) thom. G6 with Yutex deleted _Subsaph_: 1° _from a _Stip Vorter Set Vj; We delete a. Esa qubsat OF NY & al] _edges_which_have f vertet_in Vas an end point__then (G0) is called as [verter deleted 7 sulofraph _ ar eg Tigo deleted —subgre | (G_E) denotes tha _ sve y and edge got _(E- edge doloted subgraph 6 al zl Complement _o€ a Susp ae graph G6 dofined | The Com, jement G oF O— piel same Vertes ot qi ri simple graph withthe @ and whore two vertices AON A ore_afjau in G. y i £ only whon thor) ave not adjacen jr a ZN nN vu S| = | oe q 5 bya —— Bade ge 4 al Graph Gi ier complement of G. Find tha Complement of the Following) graphs: PT Lee \ Complement oF jvo frst Biaph — Vo Me aaa { —— fe oO | a = | C —| ie Ase —| Ss a at << i Complement of tne Second draph. Ny Now Sa " Ny Va = Complement _of athe _glaph ts Zt : Qt Pee ig SS < a Se eS. Bxh WS, Bs Sole Corpplementory_ Guapo: [A graph @ is Said to be Solt Cormplamentany rz n gtaph Gis isomorphic to G 4 SZ l= 3 Graph & Graph i classmate -Feamorphic Graphs : qgomorphic_is_a property which establishes the. past that two geometrical pigures gr0 Monte -qeomexphism_in graph _theowy_means_that Ho graphs ave equivalent or “Tdenal! fe there aT a coiespordence between thelr vertices & tholy edges Fore ‘such Mak inetdencos _are prrasewed 3 vf: Agron Gc CWE) _is sag to_be Ysomorphic_with Ga c (Vaeb2) if there 16 a one- to one | covrespanden —|potweon the edges fi @ f sudo that if @ is a | o with end Vertis wd Ua _in Gy then tho 1 covrespondi algo Orin do has ite ond _ypolnts- — [ae Nortic&s Vy & Vo in G2 which cowespa 3 | 8 Ue erespecti val. 1 i ty vi a S 7a at —S Vv Co Gy _ Graphs @ 4 Go are isomorphic.- ae Po phic then Gt 4g Two graphs Gi & G2 are {som oy} have tho __ @)_ Same number oF vertices @ Samo number of edges _ vertices with Same d ® equal number of Qo ex. ove ; 7 2 — oe mo re 53, —— @ ¢ 3 ‘ Gx ‘| O an Graph Gi, 4 Vertices In Graph d2 also _4 ‘Vertices - 2 @ In Graph Gi, 4" edges. ; a gyn Graph G2 also 4 edgos al F al @ dn Graph Gr every vorie® has dogreo 9 4 degree af adel Vantur {s0) 19 Graph G2 also One-to - one qirespondance between Vert!cos: ty Go 1 Slumber oF Voter in G €G@2 =y | —"@ Number oF edges in Ga&qo =y —[@ingnumber OF Vertex of degree 2 =4 Buk | in G2 _No- oF verter of dagreas =a A | 4 verter of dogreo 1 & 1 vortex of dogree 3 | which does not “eaist in Gr. \ Hone Gi & G2 are ‘not isomorphic: a aX was q G2 Mo-0F Vertex in Graph @ = "Gnph@ = ¢ - No-of edges im Graph G@ = Suphi2 = 8 OUt of 6 yorties ING 9 Verter has dogrera KL 4 Vertex has degree 3. Ur of G vortles jn Go 2 verter has degree 2 & y Verter has dogree 3- eee [ | : 4, T i —H ; i all Show _t| I Be fe b G2 has Woo “rfangles Vi Va. VOVI and Gio “ie Gute Va.» osent i +o grap) a But such arangtes are nor Jus Huo graphs ave Mot. Seah Examples - Show that given ven pais 0 oF b “graphs ove I are isomorphic. ome = | 019 ip ie + i Li I] og @raph Gy number of Vertee ind) = 5 Number of verte® th Ga- S Humber of vertex-adges in G) = 5 Humber of edges i Go = Degareo Of p Verte m0) @ = 2 eae Qhe- One eee site a —>al qd —— Bb b— ¢ @ 9 dl ec— e [a hs Tso eee Gpow Mar the following graphs are isomorphic: ~ Consider Graphs @ and Gr Mhore ore to vertices in GaG2 & Is__ edges in “gph G1& Gx [Shumber of vertios of dogrec 3 are to iin bot arephs —| Adjaceny also preserved — Qf dy be bi —» go ey —> So by — & | CG — yo A — an VW —s> do 1 Graphs G14 42 are igomorphit. - those 3 graphs" ove jsomovphit- Hence. Graphs are isomorphic . G)|_Show shat the fall » ZS OL ws AH qe 7 is rT = Consider Gaphs Gi & Go Fy mumber of Vertes in Gr= 6 umber of Vertes in G' = 6 |i plumber af edges inG = 9 7? \umber of edges in Qi = 9 fp . (iy Desire af each Verte in G@= 3 | i Hoqree of each Vevter in G! =3 Adjacency also proserved . Tsamorphic Mappitg a: VG) VG) oS al > fl > b 7 c —- e! _ = dW Ale |a>\a|o|P * Graphs @ &G' ore jeomor phie ee ho Graphs @ and} with vortex Sols -VC6) & yc are drawn bolow. determine wherhor or mot are _Isomorphic- é ; : = Ze they are isomorphic give a function ~~ [as vea) —> vc) that _dojgnes the isomorphism >< [ae chey ave not hsomarphic~ expla uh they Ore b ———_ q Ee & \ . : x ; 3 © — +4 _ t——¥ ——— | Gioph aap 1 =. i) Number of verlex in Graph G = Number a | |“ in GrophH = 4+ __ ily Mumber of edges in @iaph G=4 umber of edges iD Graph y =4 [iiiy Degree or each vero in Graph G-92 Z ! Degree of each verter jn Guph @-2 _ I Adjacenyy also preserved. i 9: VEG) —> Van) 9 —t d— V nine whether Graphs @ & G 7 ; fy yout nignees 4 & Gare isomorphic-or ‘net Se = - : me Qs 1 a Ny Go. i) Number of verter ip @ = No- of vertee in@ =6 pi it slumber of Vertes edges In G1.= No-oF edges in G2 = & ji) Th Graph G@, 2 Vertex has degree 2 gn Graph Go , 2 Verte® has degree 2 Gy Grapb Gi, 4 vortee has degree 3- gn Graph Go, 4 vorter has dogree 8 - In Graph Ga ‘There are 9 Arisngles WiaVevi © VaVe Vag Bur such ‘Arian gies are not present in Graph Gy. alah Thus 00 graphs ore Not isomorphic - ___©| TdomiFy_whelher ne _ Or not @ = oe 4 = q G S i) Number of verter io. Graph Gr = S 3 Number of vertex in Graph G2 =s c ii) Number of edges in Gaph Gr= 6 & + umber of edges in Graph Ga = S Graphs @ & @) are Not Tsomoyphic - AN : << o is a a inl a i Hl el i oy Ny! Vy yO moreno mereese WOT ES j o.of Vortex In Gr = No-of verter in Ga = 6 cof edges In 4) =No- of edges ih G2 = 9 fy 0 verter has degree 3 in graph G@ ¢_ gacd verter has degree 3 in G! also. Adjacency_alss presewed . NG: veg) ——> VG!) |_ — uy —VI Yo —— Ve [ ve ——> Vy us —— V6 —T uy — > \s Tue —? Vs \ - “|, Graphs @ & Gs ave feomerphic . 6 =a} | Graph G 1) No. of Veitox in G = No-of Vortex in Gl= 4 : fy No- of edges in @ = No-of edges in Gt= S i)_2 Vertex has degsee gin Graph Ga GE 2 verter has degree 2 in Graph G 4G! 9: VG) — VO") a——>»_ b —>m a © ——> 0 Jo di —> yp ere ieee Graphs @&G! are isomorphic - r hs on vertices 248 ON = G: SDraw al) fsomovphl< Net vic. araphs aN \ = On 59 ky vertices: << Pennines od es os 2 aR Draw al) isomorphic graphs_on. erie a Qsgo draw all non- So |_Lsomorphic guaphs_For 2 vesties SS ar ee woe oy Ny 2 are_isomorphit graphs. (3) Diaw al) won — isomorphic graphs an vertices 2,344.) = 0)9 A) non - igornorphic. graphe on 2 Vertices. o— 2 ° zs Gi Go. A on- isomarphie graphs on Q vortiies - All Non- isomorphic graphs on 4 Vertices - Ga G3 ° ° o———O TTP Re © = / o 3 & i WW eit nga © 0 eee en ee ae | ° 5 ° ° = _o 4 “¢s — “e} ° 9 ° rf ; b—}<* -} -E Gt % 4 i _4 classmate. epresentation OF Graph 3- qacency “Mobiix t divnensiona) mati can be used 10 store graph G=(Vse) wher V = 3 oto, --- en esented usinp a two “dimensiond) integer y oF ‘sige Kn: indicates presence of edgo horween o Novtices TAS NSS ENE \ "between 4wo Vortices Lai \ indicates _Gbsence oF _adge 5 qepresentad using a Square mahtX of an _und{rocted grap Adjacenyy matrix of 2 directed graph is wiever indicdes directed edge from ady CGI <4 verter 4 Adfacency ahiz ts given *Y ; Vi Ve Ve Vy Y fo 1.0 1 \ Nore |b SOsencl 20) v3 On 1010 al vy ,o 1 oO 2 wo “aan Ea V cont a@rik s_ given bi \ ag ga 4 mL a Wve Vo Vy Vs ry f ot | 0 0 4 Ver Non vo. fit iho! 2 “4 ~ Na tovh wo toni vy o 0 ot Vs oo t t 0 ry Gz==O — C) 4 Aajaceney Mairi of a directed: Graph . = T Zs Oy _ Adjaconcy Marie is given by | x + J 12 9 y- \ 1. 9 ‘ p Oo | a2i]iio | 0 g $ o 9 0 4 ! Ovo bg’ + c i : ° : 4 : Adjaconyy Malte is diven by — i. i) > I \ J Mi Vs Pe wl Lo Ye Vo > djaceny ahi Representation of \nlorghted Graph For weighted graph , the __matnat adj CICT_is croprosented as - GP there is an edge between vorties jhe = Adj Cirjd__= welghr oP the odge Cif) othoww Adj TItiJ_ =o 9 oe ( ez. » 1 1 N “| 2 Nip - fqhied grap Sai? |_ Ad agen manix of a nol Wve vg vy YS VI O Q 3 oO Qo . @ Va [2 wists’ 2 ° V3 3 Is 0 © 13 vy ° 2 0 o q Vs ° ° 13 q ° oO tS \ 4 0 +4 4 Adjacenyy "ahix is given by | a b cc qd mt oO 6 oO | 0 b oo fF t © t ' 0 1 fq Co 2 4 o | 4 ge djaconey “Wate is given tw = 0 i a6 he \d ial ° ft o © b oo | 4 c \ oO ‘ q {3 ! \ 0 ui eI, | 2-5 eG t Ver VV Ve vy Vs vwfo oo F o } : < > wy wy Mabie Naif 08 “eI 0 Adjaconey “YA Bey wo a Wy {o 1 o 0 J — al vs [1 br oO 1 0 4 Incidence “Mahix Ppa xc = Lali) of z “iphavo, ee Tneidonce Mani is given ST - @ @ 3 eh es 26 Vii aga) cal ORCI | Vo Qf~~0 > } 1 0 V3 ! 0. 0 oO oo J Vy Go a © a 1 1 VS oO 1 6 ! 0 0 Deogsoe of Verte vy = Degtoo of VerloR Vo =4 Degree oF Verter V2 = 2 Degree of Vertex Vy =¥ Degree of Verte Vs = 4 ( A iow of TWo Graphs ¢ Bperation on Graphs SNe nk ea for S1= City &t) and @o = AS) be: any Wo given raphs. Then the union Of two graphs J is denoted GUGo Whose verter sor” fs ViUV2. @ edge ser» et pve oO ine aa Graphs 6; a Ga + Wis 3 WNo% Vo = 9 Vo, Va Va 4 = eney Ex = 2 ea, ef 1 Thtersection of, wo graphs 4. = CW.t) & Go= (a, Es) ig a araph wheso Vorte® ser is ” | Vinvs and edge “set Is En TE GoGo ave edgo- disjeint giaphs ten Gin Gas ul) gtaph- a TPG & Ga _aro verter — digoink graphs the Gin G_ is_an onpry Sot: y Ge 2a d= as ef «Re Cy fe me Cy ae te Gy Gy Tntersecton GF Graph GING. Be Noe Ys | Ring 0, I> um of Wo Graphs § GO Gs e ig Ring Sum of two graphs @y="4W,E} and Gre {Vebet is t graph consisting of ¢ Ch) Verter Set vy UVe_ | cit) Edgos hat are either im Gor Gs but not fo a { | OE SSS I ee = noval of an. i : i — Sis ame a & bo o Hy G(VsE) « tok e€ . a ph_ GC Then the giaph C@—e) can be obtained by 7 remevinty the edge 'e from the graph. = ee | ef s gy % | V3, 2h oy i ‘ge ey Ny | B q-e I 3 | Removal of Nertex 3 | | ket GCE) bo any giaph @ leVeV™ | then graph CG-v)' can be obtained by comoving |_+he Vortee Vv krom +he graph @. ~ | Removal of VY Means , removal oP an hose | edges which are Incident on v. | t Ny &, ey y oy “4 (aula —aples . iro ey Ze pag “yp e4- hy, classmate ) . \| 3 rte + 4 Egarmples 2 aes {hat ig_intersecion oF ‘ss Complote graphs ke 4 kn. Ka Ttersection gives kg ZA at So, Ka ky = Ka [Paths & citcuits ¢ i bi path: A path C What) tho graph is a sequence which T has Verticos @ edges arranged in plowing? manner [No er Vy @o.5---~5 eb (Ny) And Vo.v,----- Yo EV &ss py ‘ —| Q),0n ,--- ep EE —| & fou gach i=l ton, — | the ond pots of o} ate Wei &vi —| We say Yat this path [rem Voto Vo. } pes clascmaes ON Q Dye Length of path ¢~ The ro of, cdes_1s called ag z songin. of, the path. ———__ cimple path . A path is called 9S P yt vopadted Gimple path 3- ic! edges are no fs in_path Ejementary path 3- Ho. mopelftion of vertices Cireuit 8- A_poth becomes droit if Vo=Vn “| Simple cioat_g- “No repetition of edges . Ho mepeuition of Vartices- Elemomary circuit 8- FA_cyctic graph §-_A__gtaph which does not ___ containg any circuit ennected Graph =P here eis a. put botwen — pair oF Vertis. ever |_ Otherwise the graph js disconnected. Geamplos +o, ee paths are i) VotiVi0aVo 2) Yooh 8) Voes Wo 4) Vi21 Vo @VI Ci t ap rc) Mi simple path prom A toc. m= 3 AY et 1 Wai =} AsXsBsY, CY -| i ; sci) AM: cycles 2 BS YBY AN, X.BsVF 2X8, 44 en Es J AoW, 8 XsAT t yl _Circuits : A path is called as circuit HP" TH) Begins & ends at the Game Verte® 'v'. (i) has Gtleast one edge Gi) Uses No edge twice UW) does not use any verter twice e&cepr the yertes ‘vie | = | 4 —|_ Citcurt T= Ue VeoW es W i £4 —|_citcuftir- yeywes tec ec —| i es — e Ee. sé[ Connected and Disconnected Graphs oxy Gioph is Connected if there evist a path between every pair of vortices. Othdwise graph is disconnected } L 2xX~ Connected Graph Disconn ected staph ip © Pf eo —6- —~ jas = ic 4 \ || every two Vortices aang |b in the draph Strongly Connected — A directed graph fs Said +0 ba Sirongly connected if for Merde is path promo _a te _b as well as “path _jyom b> aE | weary Connected - “Graph whieh isnot stronald” a bleatey Connected. connected is called a5 _ ples. tee na a t ~— [ Oo» p as a Loc 4 i: a a — fh S43 | Gr- Strongly Connected Qa— bleatly connedted . \ 3 t - F —aittonian Graphs _ \ i Ham onia v Grap WS = i Ci +t y gnitonian. Cycle in wet graph G isa cycle which contoins | > Y eee YW verted _Vertet of G. Mow — tt Ye | namin ig a graph G is called Hamiltonian if tt 7 it Nas _a__Hamitronfan cyde | rt a Gxamples 1-4 ql ceame tt | Z| Homittontan Graph Nest _ Hamiltonian Graph. I | : “4 | rj —] = | . = D -O-E ; ; 7 #) Hamiltonian part & cireutt = [ Zi Hamiltonian path - A path ing graph. G isa Hamittontan pam ie it contains every Verte or G exact ance- } 2 [Hamiltonian ae - A Hamittonian cl de ina _graph is | | cycle oan comains every I __|| Verter oF the aw : a | /_ 19 clissiite = we Eulerian paths & Cirwit TS *//Euterian path - A path in a graph @ is_called an ! Eulerian path ever) edge of the | Groph 6 appeats exact) _ once 'in_4tho_path. «| Eulerian Circuit —-An Eulerian ae ina aby | is _a__circutt_ which contains avon edge of the graph @ eracti once: 7 ] | tH a -Theoven 2 A_graph posses a Euclerian_path if and T only if it ts Connected and has either | | vero ov lo vortices of, edd degree. Theorem Lar A. graph posses a Euclorian circutt jf & sal | if it bs connected & its Vertices all op | even degree. Theorem! pr A directed graph possess an Eulerian circuit | if. jt is connected & +tho ideoming of avery [ettee Is cunte te angen dee #1) Example | 5 | | | t Gi dl) = y | Graph @) is Euterian pat since it has two Verto dhe | ok odd doq nee be, 9 toa [- A yaph G is NOt ao Eulorian Circuit -beacaus @=2) e Not Of, wen degree. (y dye gd fee ees / Graph Go dt) = y" did) = 4 db)= 4 die) = 4 a dO= 4 de) = 4 Odd _degree- | Giaph Go is Eulerian path since it has zero Vorter of Graph Go is Eulerian circutt since it Ts connected & Qu Vertices are oF eVon degree. t tT TT. {check whether the graph has an Euter circuit, €uler path, | Tustify. < dtapde tion d= 4 | [ae dee) opis acd) = 4 Graph @ is, Eulerian path beacause c__it is conne & Xero verter of odd degree. ey] Graph @ is Eerian circuit beacause “qe, it is _connecte] Kai) vortices of 6 eyon dogree- Ls Graph I 4 oI “degree odd G is Eulerian pirutt beacause it has al | vatter ob even degree - 2 | Theavem jor Hamitton path _& Hamilton Circuit — Theorem a TF the Sum of tho dogree fur each pair of Vertex Pia zn-1 then their eaist.a Hamilton path. heme “TF the doqiee of each Vortex in @ is dw) 7a]. | this | thon @ Will contain Homitton Circuit: is_sufficient ‘condition b aoy9 “examples - ip end “| Determine wWhethart trampaitowing? gtaph has a_ Hamiltonian — citqutt Hamitonian path. . (n3 3h D dgpri is | an Gtaph Go, n= $ es L Hamilton path a 7 Tn “tn Graph @, nes Su Se a sides Cit 0 ea hear meni dM td®) = 319 = 6 ye dcH)+ 42) = 343 = 6 oi Hence it is a Hamitton path. n-l=6 — | Hore Su a mMof dogree of each palt of Verteris not wh-l | Hence there fs No Hamilton | path . Hamittan Cireutt | an Graph Gi, degree of each Vorter ie Tes dues 7 os dQ) = 3 725 gl. d® = 379s" z| dW). = 370-5 bX el dts) = 4 7) es i me || Hence it 16 a Hamjton chreurt fib tT Graph Go, N= woes = ee = 3.5: fab =Wb=Corb= ¢()=2 Vertex Connectiviy of @ DCG) > Edge connectivinl of ¢ i & > Minimum degaod of a Verter fra graph G. ir elation between edge connectivity , No- of edgos & vortices + 5 t : . 4 A@ < 28 fe 0 ‘ { Tf _ Where @=No-of edges & Ir NL = Mono vertices in graph G. ih Examples - Find the Vertex Connectiviy KC@) A Edge Conniachinh| XC). - oN { |'To disconnect the gtaph smallest cukset should contui | 8 edgos. f — _ : o Vy Complete Bipartite graph Ka,9. 2. AQ) = 3- Ful it TP we remove vortem Vs, Ve,V4 thon the giaph wil) i i | be disconnected. H keg) = & (eee erat ae feed ind tho edge connectivity of 9 pb Tota) no. of edges = °9 —= na) < | 2¢ n . NMG) Yo a Remove edges. & Ww the graph is disconnected “RA gr0ph G is said to be Planar gtaph , iF iW can be dradn on a plane without intersecting the except at the common vortices - rae Graph ia _- ne Ce : rt 5 L i ! A . a a Hl 25 Suppose, we diaWa_ planar gtaph on | eee a plane & cut it along the edges |, al ————jhan the plane will be divided into | —| “pieces _ that Ge called Regions — 4ho_ graph. l ~~ Aumbers_indicafes region. _ Stay faving’ 6 G_eqion. | Eulors Formula $— Kor any Connected plan [Veetr= a] \ V= Number of vertices —— e= Number of edges “T= Number of aegton Aheovem TP GOVE) ts simple connected planar graph then @ < av-6 Evarplas — By drawing the graph, show that the folowing | graphs: » Care Tapbs-_ aluiot — Planet ar Ip. E Shortest Path Algorithm 3 oe DiKSS Algorithm - el as] ~~ th bu ust ijkshtr : Q-| find ho _ Shortest path by _using @ijkshtras oh » yaas | a 4 £ —wol> | Step - p= T= Aabed, oF 24 kid= 0 LOO = @, VaeeT , &$O Step 29 - lek V=a The permanent: ldbel of A =O P= a3 - ge 4 bcd, GF E% LOb) = minCo, of =o - E [AO = nnn Co, op =1 : -Atd) = min (00, 0+ 4) = wae Lie) = min(o, oto) =o LUP) = min Co» 0+) =0o — _ LW = minlw, 040)=0 istepo-tetVe co _| Me permanent label oP cy a P= Yact a I T= Abd ahszt : I LO) =" min @, Way =2 | I | ED = min, 149) =3 Le)= min Co, Its) =¢ LW = mNCo, 49) =8 LC®) = min Co, 400) = oo Step - v=b " The permant label of b= 2 V pe {acabt ge 2ae6tt [kt = min C2, oto) =3 | Lie) = min le, 3D =aS Lys min 8, ato) =8 LCD = _ min Cw, ota) Step s - Ved qhe permanent abd of d=8 P= BUebdy 1 [_ Te Leese to ft LO) = Min (sy 80) = 5 [i ‘penmanent tebe of @= 6 — pe qaeb dey _ T= AFtEY i LCE) = min (4, 6tov=t | { i Lz) = mind, st) =6 Step - Vad : Set nanan The permanent tabd of I= 6 f Lis 6 Q& Shortest path is abet | Hence the | length of Mo shottest pal |yom ato ¢ | 4 b 3 a yay 40 yeni oe anne min} ¢ ory = ap min {os OF 16d = ie min jo, o+ 64 = 8I_ minim, OF oJ = Cc = minjo, Ot Wp = th minjo@, oF ®} = © - ermanent Jabel of d= 8 pp = Bod _ i T= fibres heh ; ai LO) = min} 295 oy = - LW = minX 65 BtlO% 7 LO) = min} oe, eh so [oRP= min} ©, Oey Sol] 1¢z) = min 4 o,ao % =o “a = min } oo, da = s Laer Ve PF a - ermanent label of F = 14 PE i | TE LOY | kb) = min 020, 4tloy = Oa 2 hed = min 3 16, 443% LEDd= Min } , 14} ey: sep 6 - Veo. a 3 permanent labe} of C= 16 P=? adiFacy TH Yb EY Lb) = min} 22, Ueto} =2¢ LOV= min} oo, feted = 22 LG = min} 23, w+to y = 26 Step 6 — Vee permanent labol of e= 22 pe Fadi cet Te A bt kth) = min} 96, 02+2%3 = 4 L(Zz) min} 96, 29+4 % = 26 Sept — V=b permanent lobel of b = 24 pe jad FOeby C4) = min > 26, +24 = 26 Tait + Greps - V=# permanent abe) of Za 6. iii “Hence the length be sherbet pa is. —Rhoviest path ts \s Qn a 2 ‘Io xj? -| Stepd - P= 2 Oy: C= 3 G51,9,8 4sSist L(g) =o LOD =0,V RET.” Stepo - W=o TH 310939, S16F _ _ Pe 40%: The permanent tabd of o = o LQ) = min 3», LW) = win 2 ow, LiD= MN ow, LUD = min oo, | LD = mind o, \ 4 T= min} ©, oF eo} = co classmate C===O t sere — _ \ Seps—-V=\ canny hr The pwmanent abd of 4= ¥ { p= 2 Oty { T= 31253.4 25163 | Lt&)= mini o . 4+ Ft} = LUD= mini ©. 4+ oF = LUp= mini wo ,y+ of = Luo)= min} § ,4+6 F = LUD = MINZ co »4+poF = {SSS Wen ees Stepy 1. Va S The permanent labo) oF S= 8 — P= 4 Ost Ta 4 25354 56F LO = ming Ny ati} ase Liay= mind co, €+ 0% = o La)= ming a, OS 5 1a i Le) = Mini, 8+13 "= 4 : Siepbs V= 6. ; : ; [as qThe permanent Yabo) of 6= 4 p= 4 Onsiey 2 T= 3 BB4% Lw)= minz ns 44 ty = Ass Ming we 94235 = ot= An)= ming 2, 44 Step 6- V=3 The permanent label of 3=1) p=!) ons 6st T= 3 24% Lo= mings WN eS min} o Os Wt le Per it Step }- V= 2 jhe permanent jabal oF 221) P= 13 oh5 6. 3199 a Sah «pee job of = OF = 13 051,531.39 say Hence the — length he “the shortest “path= = 9) ae Me Shortest pair _ is

You might also like