# Graphs Rosen, Chapter 8 Isomorphism (Rosen 560 to

Graphs Rosen, Chapter 8 Isomorphism (Rosen 560 to 563) Are two graphs G1 and G2 of equal form? That is, could I rename the vertices of G1 such that the graph becomes G2 Is there a bijection f from vertices in V1 to vertices in V2 such that

if (a,b) is in E1 then (f(a),f(b)) is in E2 So far, best algorithm is exponential in the worst case There are necessary conditions V1 and V2 must be same cardinality E1 and E2 must be same cardinality degree sequences must be equal whats that then?

Are these graphs isomorphic? a b 1

2 d c 4 3

a 1 b c 2

3 d How many possible bijections are there? Is this the worst case performance? 4

Are these graphs isomorphic? a b 1

2 d c 4 3

a 1 b c 2

3 d 4 How many bijections? 1234,1243,1324,1342,1423,1432 2134,2143,

4123,4132, ,4321 4! = 4.3.2.1 = 24 Are these graphs isomorphic? But not all 4! need be considered

a b 1 2 d

c 4 3 What might the search process look like that constructs the bijection? Are these graphs isomorphic?

a b 1 2

d c 4 3 3

1 4 2 Connectivity A Path of length n from v to u, is a sequence of edges that take

us from u to v by traversing n edges. A path is simple if no edge is repeated A circuit is a path that starts and ends on the same vertex An undirected graph is connected if there is a path between every pair of distinct vertices Connectivity

a b c d G1 ({a, b, c, d }, {( a, b), (a, c), (b, c), (c, d )})

e f i g h G2 ({e, f , g , h, i}, {(e, f ), (e, g ), ( f , g ), (i, h)})

This graph has 2 components Connectivity a b c

c is a cut vertex (d,c) is a cut edge d G ({a, b, c, d }, {( a, b), (a, c), (b, c), (c, d )}) A cut vertex v, is a vertex such that if we remove v, and all of the edges incident on v, the graph becomes disconnected

We also have a cut edge, whose removal disconnects the graph Euler Path (the Konigsberg Bridge problem) Rosen 8.5

Is it possible to start somewhere, cross all the bridges once only, and return to our starting place? Leonhard Euler 1707-1783) Is there a simple circuit in the given multigraph that contains every edge? Euler Path (the Konigsberg Bridge problem)

c a b c d a

d b Is there a simple circuit in the given multigraph that contains every edge? An Euler circuit in a graph G is a simple circuit containing every edge of G. An Euler path in a graph G is a simple path containing every edge of G.

Euler Circuit & Path Necessary & Sufficient conditions every vertex must be of even degree if you enter a vertex across a new edge you must leave it across a new edge A connected multigraph has an Euler circuit if and only if all vertices have even degree

The proof is in 2 parts (the biconditional) The proof is in the book, pages 579 - 580 Hamilton Paths & Circuits Given a graph, is there a circuit that passes through each vertex once and once only? Given a graph, is there a path that passes through each vertex once and once only?

Easy or hard? Due to Sir William Rowan Hamilton (1805 to 1865 Hamilton Paths & Circuits Is there an HC?

HC is an instance of TSP! Connected? Is the following graph connected? G ({a, b, c, d , e, f , g},{(a, b), (b, c), (b, d ), (c, d ), ( g , e), (e, f ), ( f , g )}) Draw the graph

What kind of algorithm could we use to test if connected? Connected? G ({a, b, c, d , e, f , g},{(a, b), (b, c), (b, d ), (c, d ), ( g , e), (e, f ), ( f , g )})

(0) assume all vertices have an attribute visited(v) (1) have a stack S, and put on it any vertex v (2) remove a vertex v from the stack S (3) mark v as visited (4) let X be the set of vertices adjacent to v

(5) for w in X do (5.1) if w is unvisited, add w to the top of the stack S (6) if S is not empty go to (2) (7) the vertices that are marked as visited are connected A demo? Some measures/metrics of a graph

Some interesting problems in gt easy Shortest path All Pairs shortest path (apsp) Minimum Spanning Tree (mst) Maximum flow Stable matching

2 colouring not so easy Chromatic number Graph colouring olour the map so that adjacent states are different colours, with as few colours as possible

Graph colouring Instances of graph colouring Timetabling, scheduling, train timetables, register allocation, Timing sensors on a network, Independent set

hc & tsp Some other gt problems Dominating set, feedback vertex set, minimum maximal matching, partitioning into riangles, partitioning into cliques, partitioning into perfect matchings, covering by cliques, HC, bandwidth, subgraph isomorphism, largest common subgraph, graph grundy numbering, weighted diameter, graph partitioning, steiner tree in graphs, max cut, network

eliability, TSP, chinese postman for mixed graphs, rural postman, minimum broadcast ime, min-sum multicentre, stable matching with ties and incomplete lists, 3 colouring . fin

## Recently Viewed Presentations

• An air-track glider attached to a spring. The glider is pulled a distance A from its rest position and released. Fig. (b) shows a graph of the motion of the glider, as measured each 1/20 of a second. The graphs...
• Importance and Meaning of Phenoptosis Giacinto Libertini M.D., Independent Researcher, External collaborator of Dept. of Translational Medical Sciences,
• quantization, encoding. Extensions of PCM include DPCM and ADPCM. Pulses can take only . finite. number of values. For example, binary pulses can be either 0 or 1. Easier to detect at receiver (50% chance!) Pulse Code Modulation (PCM)
• Humanism and The Printing Press Unit 3, SSWH 9 c and g How did life change during the Renaissance and Reformation? SSWH 9 c and g Explain the main characteristics of humanism; include the ideas of Petrarch, Dante, and Erasmus.
• Early career clinicians often rely on System 2 thinking: it is effortful and analytic, and allows clinicians with less experience to work through a complex case to generate a thoughtful and appropriate differential diagnosis. With more experience, clinicians develop System...
• Use Search bar to find My Receipts. The My Receipts page will display all receipt transaction created by you. There are multiple search filters you can use to help reduce the results displayed. An alternate page that can be used...
• Mission Statement. The International Baccalaureate Organization aims to develop inquiring, knowledgeable, and caring young people who help to create a better and more peaceful world through intercultural understanding and respect. To this end the IBO works with schools, governments, and...
• Li égése Na égése K égése Na reakciója vízzel Na és klór reakciója NaCl-o. elektrolízis bruttóegyenlet (Hg-katód) Sütőpor (szalalkáli) bomlása hőre Sütőpor (szódabikarbóna) bomlása hőre Szódabikarbóna megköti a gyomorsavat Hypó és sósav reakciója NaOH elfolyósodik (reakció CO2-dal) Magnézium égése Kalcium...