Isomorphic graph

graph

1. presented BY: UMAIR KHAN

2. T opics i n di s cuss i on      I n t r oduction t o Isomorphism I s omorphic g r aphs Cut s e t Labe l ed g r aphs H a mil t onian ci r cuit

3. • I s omorp h ism Isomorphism is a very general concept that appears in several areas of mathematics. The word derives from the Greek iso, meaning "equal," and morphosis, meaning "to form" or "to shape.“

4. I s omorph i c g r aphs • I s omorp h ism – T w o g r aphs a r e isomorphic, if th e y a r e s tru c tu r ally id e n ti c al, Whi c h m e a n s th a t they c or r espond s tru c tu r al de t ails. F orm a l v e r t e x- t o- v e r t e x and e d g e – t o- e d g e c or r espond e n c e is c all e d is o morphism. in all – • T w o g r a p h a r e said t o be isomorphic if    They They They h a v e h a v e h a v e t h e sa m e no of v e r tic e s. t h e sa m e numb e r of ed g es. a n e qu a l nu m b e r of v e r tic e s with a gi v en d e g r e e .

5. V er i f y i ng Isom o rp h ic Graph V ert i ces( A ) : a b c d e V ert i ces(B ) : Deg r ee of v ert i ces: E dge s ( A ): E dge s ( B ): q 2 p 3 r 3 s 3 t 1 e1 e’1 e2 e’4 e3 e’3 e4 e’2 e5 e’5 e6 e’6 G r aph B G r aph A

6. E x amples f or n o n i s om o rphic g r aphs : i) u 2 v 2 u 3 u 1 v 1 v 3 u 4 v 4 u 5 1 st 2 nd . g r aph has mo r e ed g es than

7. 2 nd 1 st ii) g r aph has v er t e x of d e g r ee 1 , g r aph doesn't. u 2 v 2 u 3 v 3 u 1 v 1 u 4 v 4 u 5 v 5

8. 1 st iii) g r aph has 2 deg r ee 1 v erti c es, 4 deg r ee 2 v er t e x and 2 deg r ee 3 v erti c es. 2 nd g r aph has 3 deg r ee 1 v erti c es, 3 deg r ee 2 v er t e x and 3 deg r ee 3 v erti c es. u 1 u 2 u 3 u 4 u 5 u 6 v 1 v 2 v 3 v 4 v 5 v 6 u 7 u 8 u 9 v 7 v 8 v 9

9. Cut set Cut s e t is a c onnec t ed g r aph G is the s e t of e d g es who s e r em o v al f r om G le av es G dis c o n nec t ed, P r o vi d ed the r em o v al of no p r oper se b s e t of th e se ed g es dis c onnects the g r aph G. Cut s e t a r e also c all e d p r oper cut s e t or minimal cut s e t. • •

10. • If o n e c an r em o v e a v er t e x (and all incide n t ed g es) and p r oduce a g r aph with mo r e c omp o ne n ts, the v er t e x is c all e d a c u t ver t e x or art i c u lati o n p oi n t . Simil a rly if r e m o v al of an ed g e c r e a t es mo r e c omp o ne n ts the ed g e is c alled a c u t edge or bridge . The cu t- set of the cut is the s e t of e d g es who s e e nd poi n ts a r e in di f f e r e n t su b s e ts o f the partition. E d g es a r e said t o be crossi n g the cut if th e y a r e in its cu t - s e t. • •

11. Labe l ed g r aph A g r aph G is c all e d a lab e led g r aph if its ed g es and / or v erti c es a r e assi g ned s o me d at a. • • A g r aph lab e ling is the assi g nm e n t of labels, t r aditionally r ep r es e nt ed b y i nt e g e r s, t o t he e d g es or v erti c es, or b o th, g r aph. of a • If the e d g e e is as s igned a non - ne g a ti v e numb e r then it is c all e d the w eig h t or len g th of the ed g e e .

12. • V er t e x - labe l ed g r aph • If all the v erti c es in a g r aph a r e gi v en a lab e l then it is v er t e x - lab e led g r aph • E d g e - labe l ed g r aph • If all the E d g es in a g r aph E d g e - lab e led g r aph a r e gi v en a lab e l then it is

13. Hami l t onian ci r cuit H a mil t onian p a ths and ci r cuits a r e na m ed a f t er the m a the m a tici a n , William R o w an H a mil t on. A H a mil t onian ci r cuit in a c onnec t ed g r aph is d e fined as a closed w alk th a t t r a v e r ses e v e r y v er t e x of G e x actly o n c e . also c all e d H a mil t onian c y cl e s. • • • It is c all e d as ci r cuit if it includes e v e r y v er t e x of G. If a n y ed g e r e m o v ed th e n it is Hamil t onian p a t h . is Ham i l t onian c i r c u it: { v1,v3,v4,v2 , v6 , v5 , v1} The ab o v e is a Ham i l t onian ci r c u it as each a n d e v e r y v er t e x is t ra v e r sed on c e A n d c omp l e t es the c i r c u it b y ending in s t art i ng poi n t.

14. • A Hamil t o n ian p a th o r t r ac e able p a th is a p a th th a t vi s its ea c h v er t e x e x a c tly once. Its also c all e d as a t r a c e a ble g r aph. a b H ami l t onian p a th d c • A g r aph is Hamil t onian - c onnec t ed if f or e v e r y pair o f v erti c es the r e is a H a mil t onian p a th b e t w e e n the t w o v erti c es.

15. any Question

16. Tha n k you