Scribd
Upload
33 views23 pages

GT Module 4 Notes KVS

The document discusses planar graphs, defining them as graphs that can be drawn on a plane without edge intersections. It introduces Kuratowski's theorem, which states that a graph is non-planar if it contains a subgraph that is homeomorphic to either K5 or K3,3. Additionally, it covers various properties, theorems, and methods for determining the planarity of graphs, including the use of incidence matrices.

Uploaded by

ava33sh
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
33 views23 pages

GT Module 4 Notes KVS

The document discusses planar graphs, defining them as graphs that can be drawn on a plane without edge intersections. It introduces Kuratowski's theorem, which states that a graph is non-planar if it contains a subgraph that is homeomorphic to either K5 or K3,3. Additionally, it covers various properties, theorems, and methods for determining the planarity of graphs, including the use of incidence matrices.

Uploaded by

ava33sh
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
NS PLANAR GRAPHS © Issen8 Degimikion: A groph G Ss sold to be planar ub thene EXE dome guometric nepresentation of 6, which con be drown on a jplane “such thot no kuo of th edges Vinkerseck. £ graph Jhot cannot be drawn On a plone kth ae Q Crossover betiieen Sts edges i Wvon-planax A Graving OF % geometric Sepresentakion of a gph on any surface Such thak no edge tnkerseck 2s col ed Embedding Kuvakowski's Graph: mets S_Guvoopph YA Complete graph Wis 5 verticu =k, abo colled ay Kurokonski!s First graph—> Cks) a. A bipasrtee regalo areph Kz,5 Ss cabled as ~ Huratotiatlle Gated greph= > Det<[«.2 Theorems: Prove thot ke Lee us draw Ke Graph Auth brat no edges intersect, ve % C> CO J \ Ns Yo Ns Ny : , \_/ Nq i) Toph & Non-plonay Ve Vy aw © Draw the peniogon is Joh V,-Ve Vi VorMs Ma Vs Which Ni-N3 divide the plane into i os Wor We have to draw an edge bekween Vy to Vy: However eageVy,¥4) Cannot be droim inside or oubide he Pentagon poitheut a Crossover The Ks cannot be embedded in a plone: Prove thot Kyrotosk's Seema Graph i Kaya Ckuratenskt's Second Graph) can be dian Ne x, os - Ne NS see Lic us bry to dra, the above graph Without egy aissuwss ge ye Vy oO vi KS ® ISSATCB 8 suk g edges con be damn bittheut crossover Howeren edge Vai¥e Cannot be duowm unsiole Or dubidla the Hexagon Kyag gph sven planan. Ckkroce ss Kf!s seomd Yrph) eee ee ee Bla Gres. Theorems aoe Prove that @ connected groph loth 1 veces and ¢ edge har e-nyo reqtons 6 f= ena) Ka ; tro dA | Any panos HPA con be drown Auch that each regio sg poty GP» Lek the aL nek Deprmrentig Whe gph @ has ren : Pes F AOU [faces and ee Kp be the nMiumber Oh p-secded reg’, ge» Since SAS Cage or the boundaay of eso srepton Kp + bey + 5, Ks + tr k, = 2€ =o Auo , Kat ky tke + tot Ky = f-@ The Aum of oly Anglia subkended ok each vertex ty the Poly gonal Mee = 20h += @ Wwke Ban, tS Sekerter angles dy a patted poly xCpa) S = AC Sum of LL extendor = 1 as Eqn @ can oe col as BANA dum of GOD Stories anjlu of Gayeregiors and exbetor angls of 41 Snfintle Maton: F otal Sum =n (3-2). Kya RC4-2) Ky tt G2) KE oR (hem 2K = Be Bat QR Ky +t BR Kg t FAK 3) Ukm= KCKst o2kyt Ske +4) DKA Wye Kea y= on (ada $ subtract 2k tk De + 2k, ts -#0 WS Set . fa\an) hs an = 2k, —2ky- Ee -- > Gxt uky tone JEG = 2Cks tkyr Kt )= Un ie eo MS 88 4y - afta BS 2e-2F ry = Anes fe-g4s)~ Zn - €-F£ 422m ene ee Prove thak wh a Admple , Gonneded Plenos groph WU f ae all ce ¥ & edgy Pref: Each! region tU bounded by ableast’ three B COdk bebongs Ly exo deso regen, ; o4ge & * emia 20 235 © YNS sarreB Substttuke go e-n+e (euhs formulas) Ly eq) He ak ez 3 Ce-n+2) ‘ LOZ Ze-3BH46 a |€ Lh io Soh Loop oa elf, Loop 3) Penclant Fag 4) ches 7 er Sn Serius Ages form’ im ; 7 oe Poratt . vice on verse e VAbex placed bow diary 6) Faces Po 4) . Fae the * ev Eices ee oH ce 7 +) Fo . f= n* ot e=e* N= £m #8 Pre duoab of dno som nie ha are Some 9 Ok ¥ulo ASomorphic gropha Answey $ NO. Conseder the Sotlering Yromorphic quophy 4 74 | 6* Nice rok Gy BGa ane Lsemerphic bab tad dus Gr 28 on One Nor {somerphic. WE reser? Lek us dry ko find euk db thre is % Sabgsaph homeomerphic Lo Ks ork, 5 Remove edgy 10-7 and 4-3 Gnd redraw - “ DATs ie q edtu wet seles obo SA0 vjo-p in" * 239 zp edges On in Sales abo 2747.9 eG Can be Sedraun as: 6 2 * This 8 dndeed Homeomaph 4 3 ko Kas oF Kurostouss kits 7 lo 9 4 g Second Tp. we By Kuratouwsks's theorem Ruerson geoph Non-planas, Matrix Reprsentakion of Graph (1) Tndclence Motix: LA) Le G be a graph with m verkion ,¢ edger f no Self (oops, An inddence mohix bon nxe matrix Az Cozi) where =a Sg J edge Gu Gncidenk on 1% verkex ve og =0 Sthenise. xy ab cdesf gh Oo 9010100 o 0 OO V4 4 o 9 OOOGN OL \ { toltlaoog o © }1ag1o 1 1000000 Each column of A ho exady Lwo 1s, sence every edge & tincidunt 6n so veatices ~ NO. Of One th each rox = degree of the Corresponding Vettes — B Rov with oh ds = Teelaked vertex ~ Porolleh edges = Zdanttool aLumns Permukotion of ony tuo rows or estumns corrupondy bo vdobding the ver and edger of G. ~ Th & ds disconnected (soy 4,8 9, Components) can be Wrikbern Caf o 4 CG) = fae aca) Black dfagnot. forn, — GIG, one Loemerphic Sh thar incidence mamicas AGH) 2 ACar) dd yser only byj permukahins of rot & Columns, (ST Rank of inddance matrix ACH) = nt) Prooh. Each yo fy ACG) Can be regarded o4 ov vector AY nceye le An Since there are exadhy two I's th every Colum, Sum of, all thue vedors bb o @rodulo 2), 3. AVAL Ay One. rat Mncanly dndapertent.(2 Rank of AZ AAO Th G & Gomneced, ACG) Cannot be porttimed au Acq) with mM vous 9 AC9,) wth Gm ont. Le, nro mann Avbmodix Can be found fo that module 2 Sun, OF hose m rows Lu equal to Zxo- Therttore ng Linear —combinakion Sh wm son webors of a berm en) : 5 T-5th = 3 chords Each chorck ik have Jeoreapents ty ene Fund Oke Fondameval oa @ : Peenen ed @: Le, eeu} ee - ioe 8. = 3 Fele, e, ee, FQ)! 0 o Neca eared @ 0 \ Oo; 19: 20 Ob Ceo | Oniomeyiny & Tdinkty matrix Branch of, Spar OY orca Mee-ntt Tree From © We Know thar Rank of Bp ay Pho, wee Sine Br CB, Rank of By < Rank of B 4G Rank of BZ Rank of © => Ronk of BZe-nH Kus $ @ ~ SSS Theorem : (Prove thot Rank of B= e-+ ) Proofs wie From sylvester Meorem ; A+ BT= 0 (mod 2) (A= mccdince Motets) Yank Ob A + rank o, B <¢ Se rank % B< e_ronk of A> @ Bur ie TANK of A = m%] » as CSubatirake h@)rork 0) B Ze Bok © N+) Grom@ previous peye) We have York of BZ e-n+) Ak SEK madris Lec) ts Sante TrOWS Corresponds AD the Coed Sy gm eukset =0 = SeXy loop Co a Suptesp Con never be ~Pase of, any er) 2 Wery our Of stnctdence marx di hdd OS A Soy In Q Utter Matrix. 3 CCQ) Conta aca) Tonk of Clo) 2 rank oF ACG) oe ron of CCq) Zn-| —WU) 5 > © Theorems: Show thor Rank oy C6) = m1. Proohs wee Rank OF CCH) 2 Ron OF ACh) (yom) +6 yank of CG) > m4 > Gi) AYO, Since NO of edges Gammon do a Cuter § B® Ckk ve Atay. EVEN Cue have proved tits themem ih previow Chapt) > Bete CBT Greet’) : Fpply Sylvester Thevrerry Tank of B +.yank o¢ C Se Tank of C o< e-rank of B Vor 960 < oe “yey York of CZ any (ii) + From eqn (i) aa (rams of C =n) . © vy Cotes 1) L HY DX tes gh 6) ka, vd 3 Lasy ) {e,a,q) . WY Laoag Pgh Ee Lee) eo, Kus 9 9 DOH Oo |Y Ts Sens @a F198 (0 sol jy to 3/9 0 DIDO 0 4y)o 0 1 1001.0 slo o0 1901000 6}/\ 1 9009090 4}9 o oF tala g oo .vaoltlto nok “Oakeek wv Most. (Cp daoiong hve Sparing Fre = ene bmanch mony cher = {b Gi C3 Ne, ol} [Link] = No. of Branths = 1~-} considey the Stree={ ade 59h) § Branches et S F- oe. F. cones © La,by @ tyres ® Lecy ® {ths © Lg,as ChoRrDs Prange csbumns Cedgo ) Sach that Grails Come fic chert ar {b, 0, A} bedlae $+ gh Of 1 cays e000 g,-B| oO! Biles 0 090 @\| 00 vo 0100! & cp = Leet) garsjoo 81° 8, = Ua, By) ol 009 |o 2,2 wo @) . (C/ yy [Poth morite 3) ave defined hor a Spect pc por of Vertices ah a gyaph, soy CY) PCuy) = Cg} chore py et Sb pPedge bin tt pats Ne =O = a wor th > pat ; PO bln Vy SVe one they Lhogicd e207 @ O °o MOCV Ne) + tdic by, fd,9,eb) Lac a} fdg,e¢a3 ts,e03 Fes {4, 9, c,a5 (5,4 ¢ by ae Nek a Cotamn of ot os = edge Hor clos mot Ke oy Ory Pas bh, % 8 Yy- Reng sam of any dvO vos & Pay) Corrsponds ko A CKE oY on td gf hesfotng Union of ck ( Birrady prred in the Previow, Chapra) S Kore : C (AdJacenry Matria:) Coonnectbbn mati) (Xo) th a * kU A nan Symmebvic Binary moss %= Grej) where oe, y =41 thee & an =o DiRecy . 1 edge bln, UP 3 Venki, NOV 6 yey) | io. ie onto. Ny Ny SCH ciate To Lol onnirg Note!) X mot mone wo Provision for Porobter Eolges. DL aA Sh thee La SUfteop © Vertex S. 3) Th Qo a Stmpk Fophs Numbur of as by hor a On ora tobumn = Degree of he Corresponds Verte. _ , Vay & & Ks cormected , has 9 is Com porunds hen xC6) = ae 12 “eo. /xCqy)

You might also like