FT What is a Graph Graphs present a key concept of discrete mathematics. Informally, a graph consists of • vertices, sometimes called nodes ("dots"), and edges ("arcs") between pairs of vertices. Importantly, graphs are easy to draw and understand from a picture, and easy to process by computer programs, too. □ Brief outline of this lecture • What is a graph - basic terminology, examples and trivial classes of graphs, vertex degrees. • Subgraphs and isomorphism, recognizing (non-)isomorphic graphs. • Trees and forests - graphs without cycles. • Directed graphs and multigraphs. Petr Hliněný, Fl MU Brno, 2017 1/33 Fl: MA010: What is a Graph 1.0 Defining a GRAPH - a foreword • First to say, we are going to define a simple undirected graph... - NO multiple edges - NO arrows - NO loops • Not to forget, our graphs are finite. Petr Hliněný, Fl MU Brno, 2017 2/33 simpCe undirectedgroph = jednoduchýneorientovaný graf bez násobných hran, bez šipef^ bez smyček^ Fl: MA010: What is a Graph ■r 1.1 Defining a GRAPH Definition 1.1. A graph (formally, a simple undirected graph) is a pair G = (V,E), where V is the vertex set and E is the edge set - a subset of pairs of vertices. Unless stated otherwise, our graphs have finite and nonempty vertex sets. □ Notation: An edge between vertices u and v is denoted by {u,v}, or shortly uv. The vertices joined by an edge are adjacent or neighbours. The vertex set of a (known) graph G is referred to as V(G), the edge set as E(G). □ Fact: A graph is, in algebra terms, a symmetric irreflexive binary relation. □ Remark: How can we describe a graph? Either by listing the vertices and edges, or with a nice picture... V = {1,2,3, 4} E {{1,2}, {1,3}, {1,4}, {3, 4}} 1 2 3 4 □ Which one do you like more? simpCe undirected graph = jednoduchýneorientovaný graf verte?t(vertices) = vrchol (y), edge = hrana, adjacent = sousední Petr Hliněný, Fl MU Brno, 2017 3/33 Fl: MA010: What is a Graph Basic graph classes One often refers to some basic special graphs by descriptive names such as the following. □ The cycle of length n has n > 3 vertices joined in a cyclic fashion with n edges: c n □ The path of length n has n + 1 vertices joined consecutively with n edges: n n n + 1 Petr Hliněný, Fl MU Brno, 2017 4/33 cycCe of'length = kružnice dílky, path = cesta Fl: MA010: What is a Graph The complete graph (clique) on n > 1 vertices has n vertices, all pairs forming edges (i.e. (™) edges altogether): . . . The complete bipartite graph on m > 1 plus n > 1 vertices has m + n vertices in two parts, and the edges join all the m • n pairs coming from different parts: 1 2 3 4 m ■ ■ ■ m,n V 2' 3' ■ ■ ■ ri complete graph = úplný graf (ktikji), bipartite = bipartitni Petr Hliněný, Fl MU Brno, 2017 5/33 Fl: MA010: What is a Graph r The star with n > 1 rays is just a special name for the compl. bipart. graph n ■ S n Petr Hliněný, Fl MU Brno, 2017 6/33 star with rays = hvízdá s paprslqi /rameny Fl: MA010: What is a Graph Vertex degrees in a graph Definition 1.2. The degree of a vertex v in a graph G, denoted by dc{v), equals the number of edges of G incident with v. An edge e is incident with a vertex v if v is one of the ends of e. □ In this example, the degrees are written at the vertices. □ Definition: A graph is d-regular if all its vertices have the same degree d. Notation: The maximum degree in a gr. G is denoted by A(G) and minimum by č(G)a Theorem 1.3. The sum of the degrees of all vertices of a graph is always even, equal to twice the number of edges. □ Proof. When summing the degrees, every edge has two ends and hence it is counted twice. □ degree = stupeň vrcholu, incident ~ pripojený, regular = pravidelný, even = sudý Petr Hliněný, Fl MU Brno, 2017 7/33 Fl: MAOIO: What is a Graph 1.2 Subgraphs and Isomorphism Definition: A subgraph of a graph G is any graph H on a subset of vertices V(H) C V(G), such that the edges of H form a subset of the edges of G and have both ends in V(H). We write H C G as for the set inclusion. □ Why, on the left hand side, the red subsets do not form a subgraph? □ On the right hand side, we have got a well-formed subgraph in green colour. □ Definition: An induced subgraph is a subgraph H C G such that all edges of G between pairs of vertices from V(H) are included in H. A spanning subgraph is a subgraph H C G such that V(il) = V(G). Petr Hliněný, Fl MU Brno, 2017 subgraph = podgraf, induced subgraph = indukovaný podgraf, spanning = phktenující 8/33 Fl: MA010: What is a Graph ^Elementary graph operations • Deleting an edge or a vertex from a graph G: G\e:= the spanning subgraph of G such that E(G \ e) = E(G) \ {e}, G \ v := the induced subgraph of G such that V(G \v) = V(G) \ {v}. • One can analogously delete a set of vert./edges from G: G\X, G\F. □ • Adding a vertex or an edge to a graph G, for v 0 V(G), e = m/; 0 E(G): G + v := the graph on V(G + = V(G) U {v} and £(G + v) = E(G), G + e := the graph on V(G + e) = V(G) and £(G + e) = E(G) U {e}, assuming u,w e V(G). □ • Subdividing an edge e = m/; G E(G) in a graph G: - the result is the graph (G \ e) + ve + {m>e, ve^}- subdividing = podrozděíení Petr Hliněný, Fl MU Brno, 2017 9/33 Fl: MA010: What is a Graph Isomorphism of graphs Definition 1.4. An isomorphism between graphs G and H is a bijective mapping (one to one) f : V(G) —> V(H) such that, for every pair of vertices u,v G V(G), it holds that {u, v} is an edge of G if and only if {f(u), f(v)} is an edge of H. An isomorphism mapping between two pictures of the cycle of length 5. □ Graphs G and H are isomorphic if there exists an isomorphism between them. We write G c± H. □ Fact: Isomorphic graphs have the same numbers of vertices and of edges. Fact: If a bijection / is an isomorphism, then / must map the vertices of same degrees, i.e. dc(v) = dnifiv))- The converse is not sufficient, though! isomorphism = isomorfismus / izomorfismus, Bijective = vzájemné jednoznačné Petr Hliněný, Fl MU Brno, 2017 10/33 Fl: MA010: What is a Graph We shall first compare the numbers of vertices and of edges. (Agree.)□ Then we compare their degree sequences, i.e., the multisets of vertex degree values. (Again, they agree 2, 2, 2, 2, 3, 3.)n This means we have found no easy distinction, and the graphs might (or may not!) be isomorphic. We have to start looking for all possible bijections between them. □ r 9f \-* 2' In this particular case, it helps to notice that the two degree-3 vertices on the left are symmetric, and so we may choose any one of them to map it to the leftmost vertex of the second graph. Numbering the vertices by 1,2,3,4,5,6, we can construct the rest of the mapping (already have 1 —>• ]/) as in the picture. □ Petr Hliněný, Fl MU Brno, 2017 11/33 Fl: MA010: What is a Graph Graphs as isomorphism classes Usually, we do not treat graphs as particular pictures or presentations, but more generally. Proposition 1.6. The relation "to be isomorphic ~" is an equivalence relation on the class of all graphs. Proof. We easily show that c± is reflexive, symmetric, and transitive. □ □ The more suitable view of "a graph" • An important corollary of Proposition 1.6 is that the class of all graphs is partitioned by c± into the isomorphism classes. □ • Hence when we speak about "a graph", we (usually) actually mean its whole isomorphism class. A particular presentation of the graph then does not matter. isomorphism class = třída isomorfismu Petr Hliněný, Fl MU Brno, 2017 12/33 Fl: MA010: What is a Graph ^Specialized subgraph terms Notation: Consider an arbitrary graph G. • A subgraph H C G isomorphic to a cycle is called a cycle in G. • Specially, a triangle in G is a subgraph isomorphic to the cycle of length 3. □ • A subgraph H C G isomorphic to a path is called a path in G. • A cycle / path of length k is also shortly called a k-cycle/k-path. □ • A subgraph H C G isomorphic to a complete graph is called a clique in G. □ • An induced subgraph H C G isomorphic to a cycle is called an induced cycle in G. Analogously for an induced path... Does it make sense to speak separately about an induced clique? And induced star? □ What subgraphs and induced subgraphs can you find in the following graphs? Petr Hliněný, Fl MU Brno, 2017 13/33 Fl: MA010: What is a Graph □ We start analogously to previous Example 1.5. Both these graphs have the same numbers of vertices and edges, and the same degree sequence 2, 2, 2, 2, 3, 3. However, if one tries to find an isomorphism, even exhaustively, (s)he fails. What is going on? □ Which property of the graphs prevents us from finding an isomorphism? Since there are (especially for larger graphs) too many potential bijective mappings to try them exhaustively in practice, we shall look for some other, ad-hoc, approaches... This time, the first graph has no triangle and the second one has one! Hence they cannot be isomorhpic. □ □ Fact: No universal and efficient way of deciding an isomorphism between two graphs is currently known (the problem is not known in P). On the other hand, however, the problem is neither NP-hard to our knowledge, and so a general polynomial algorithm might emerge in the future... Petr Hliněný, Fl MU Brno, 2017 14/33 Fl: MA010: What is a Graph Some special kinds of graphs Connected graphs are those graphs G such that, for any two vertices u, v G V(G), there is a path in G between the ends u and v. - more details in Lecture 2... □ Bipartite graphs are subgraphs of some complete bipartite graph K c ra.n C - more details in Lecture 6... □ Trees are connected graphs with no cycles as subgraphs —>> see next. Petr Hliněný, Fl MU Brno, 2017 connected = souvislý (ne "spojitý"!), Bipartite = bipartitní, tree = strom (graf bez kružnic) 15/33 Fl: MA010: What is a Graph ^1.3 Trees; Basic properties Definition 1.8. A tree is a connected graph T without cycles (acyclic). A graph which is a union of one or more disjoint trees is called a forest. Notice that a tree must be a simple graph since a loop is a cycle of length one and parallel edges form a cycle of length two. Cf. Section 1.4... □ Lemma 1.9. A tree on more than one vertex contains a vertex of degree 1 (a "leaf').u Proof: We consider a longest possible path S in our tree T. Since there are no cycles in T, the endvertices of the path S must have no other edges incident with them (or S can be prolonged). Hence the degree of these ends is one. deg. 1 □ tree = strom, forest = tes, acyclic = acyklický, bez íqnžnic, íeaf= list Petr Hliněný, Fl MU Brno, 2017 16/33 Fl: MA010: What is a Graph ^Number of edges of a tree Theorem 1.10. An n-vertex tree has exactly n - 1 edges for n > 1. □ Proof: By induction on n > 1... • A one-vertex tree has n — 1 = 0 edges; true. • Let a tree T have n > 1 vertices. By Lemma 1.9, T has a vertex v of degree 1. Denote by T' = T\v the subgraph obtained from T by deleting v. Then is also connected and acyclic, and hence T' is a tree on n — 1 vertices. By the induction assumption, T' has n — 1 — 1 edges, and so T has n — 1 — l + l = n — 1 edges. □ Petr Hliněný, Fl MU Brno, 2017 17/33 Fl: MA010: What is a Graph ^Unique paths in trees Theorem 1.11. Any two vertices of a tree are connected via exactly one path. □ Proof: There exists at least one path by the definition; cf. connectivity. u ©--- If there were two distinct paths P\,P 0 looks as follows Definition: The number of arcs from u in a digraph D is called the outdegree d™1^), and the number of arcs towards u is the indegree dlj^(u). Petr Hliněný, Fl MU Brno, 2017 21/33 directedpatfi /cyde = orientovaná cesta/kružnice (nebo cyklus) indegree = vstupní stupeň, outdegree = výstupní stupeň Fl: MA010: What is a Graph Generalizing graphs even more. • On some other occasions one may want to speak about structures in which more than one edge exist between one pair of vertices, and the edges might have mixed types (undirected or directed, loops). □ • This leads to so called incidence model of a (multi)graph in which edges are elements on their own, along with the vertices; as opposed to our default adjacency model where only vertices are considered as the entities. □ Definition: A mixed multigraph is a triple M = (V, F,e) where V D F = 0 and e : F —>> (^) U V U (V x V) is an incidence mapping of the (multi)edges. In the definition, • (^) represents the unoriented edges, • V the unoriented loops, and • V x V the oriented edges and loops. Petr Hliněný, Fl MU Brno, 2017 multigraph = multigraf, multiedge = násobná hrana (mezi stejnou dvojicí vrcholů) 22/33 Fl: MA010: What is a Graph ^1.5 Appendix: The degree sequence of a graph Definition: The degree sequence (called also the score) of a graph G is the collection of degrees of the vertices of G, written in a sequence of natural numbers which is (usually) sorted as nondecreasing or nonincreasing. In abstract graphs, their vertices usually have no names, and so we have to sort their degree sequence somehow. The particular custom is not important. □ Just to quickly ask, why the sequence 1, 2, 3, 4, 5, 6 cannot be a degree sequence of a graph?n (Is the sum even? No...) And what about the sequence 1, 2, 3, 4, 5, 6, 7 ? □ Theorem 1.14. Let d\ < d^ < • • • < dn be a sequence of natural numbers. There exists a simple graph on n vertices having a degree sequence di, d2,• • •, dn if, and only if, there exists a simple graph on n — 1 vertices having the degree sequence di, d2, • • •, dn-dn-i, dn-dn — 1,..., dn-2 — 1, dn-i — 1. Petr Hliněný, Fl MU Brno, 2017 23/33 degree sequence = posloupnost stupňů neboli skóre grafu Fl: MA010: What is a Graph Example 1.15. Is there a simple graph with degree sequence (1,1,1,2,3, 4) ? Using Theorem 1.14 we modify the sequence to (1,0,0,1, 2), □ then sort again as (0,0,1,1, 2), and continue analogically with the next step, arriving at the seq. (0,0,0,0). □ A graph with the last degree sequence clearly exists, and so by the equivalence claim in Theorem 1.14, our graph exists as well. □ How can we construct such a graph? See... The first step analogically translates to (1,0,0,0,1, 2, 3, 5), sorted as (0,0,0,1,1,2,3,5). □ One more step and we get (0,0, —1,0,0,1, 2). What does it mean? □ Since the degrees of a graph cannot be negative, a graph with the last sequence does not exist, and neither does the original one! (1,1,1,1,2,3,4,6,7) ? □ □ Petr Hliněný, Fl MU Brno, 2017 24/33 Fl: MA010: What is a Graph ^1.6 Appendix: Rooted trees and Tree isomorphism The introduction of rooted trees is motivated primarily by practical applications in which a "tree data structure" has to be grasped at some vertex (the root), and also by historical use of family-trees. Actually, the traditional family-trees motivated much terminology of graph trees. □ Definition 1.16. A rooted tree is a tree T together with a "highlighted" root r G V(T), i.e. shortly a pair (T, r). r Interestingly, trees in computer science grow top-to-bottom... Petr Hliněný, Fl MU Brno, 2017 25/33 rooted tree = kořenový strom Fl: MAOIO: What is a Graph descendant of p if the unique path from s to the root r contains p. nAn immediate descendant is a child (son) s of p. □ The root has no ancestors and leaves have no descendants... root Definition: A vertex of degree 1 in a tree is called a leaf. On the other hand, in a rooted tree, leaves are the vertices with no descendants. See the differences between meanings of a leaf in ordinary and rooted trees: Say, a single root without children is a leaf, but in all other cases leaves of a rooted tree have degree 1. On the other hand, in a rooted tree, a root of degree 1 is not called a leaf (it has one child). parent = rodič, child= dítě, descendants = potomci (všech úrovní), íeaf= list Petr Hliněný, Fl MU Brno, 2017 26/33 Fl: MA010: What is a Graph :f;—;- Center of a tree Definition: The center of a (nonempty) tree T is the vertex or the edge found by the following recursive procedure: • If T is a single vertex or a single edge, then this (T) is the center. □ • Otherwise, we create a smaller tree T' c T by removing all leaves of T at the same time. This T' is nonempty, and we determine the center of T' recursively. The center of T is identical to this center of T". □ Example 1.17. The definition of a tree center is illustrated by the two examples: ® □ center = centrum stromu Petr Hliněný, Fl MU Brno, 2017 27/33 Fl: MA010: What is a Graph ^Ordered rooted trees Definition: A rooted tree (T, r) is ordered if the orderings of the children of each its vertex are prescribed. A rooted ordered tree is also called a planted tree. □ A rooted ordered tree can be visualized as a tree drawn in the plane without "crossings" and with a marked root. The cyclic ordering of the child edges (against the parent edge / the root mark) then gives the tree ordering of the children. Petr Hliněný, Fl MU Brno, 2017 28/33 ordered rooted tree = uspořádaný kořenový strom Fl: MAOIO: What is a Graph ^Tree isomorphism The isomorphism problem of trees, as a special instance, has already been defined and studied on general graphs. Tree isomorphism problem, however, has one additional interesting aspect — that there is an efficient and straightforward solution to it. □ Definition: Two rooted trees (T, r) and (T',r') are isomorphic if there is an isomorphism between T and T' such that r is mapped onto r'. ry ty^ □ Definition: Two rooted ordered trees are isomorphic if there exists a rooted isomorphism between them which preserves the orderings of children at each vertex. Petr Hliněný, Fl MU Brno, 2017 29/33 Fl: MA010: What is a Graph Coding of ordered rooted (planted) trees Definition: (((()()())()) (0(0))) ((000) 0) (000) 0 0 0 (0 (0)) (0) 0 The code of a rooted ordered tree is determined recursively from the codes of the subtrees of its root, concatenated in a prescribed order and enclosed in a pair of parentheses. □ Remark: Instead of '(' and ')', one may use other pair of symbols such as '0' and '1'. Lemma 1.18. Two rooted ordered trees are isomorphic if and only if their codes are identical as strings. Proof: Easily by induction on the depth... □ Petr Hliněný, Fl MU Brno, 2017 30/33 Fl: MA010: What is a Graph Example 1.19. Draw a planted tree with the following code ((()(()()()()))(()()))■□ If s is the code of a rooted ordered tree T, then—as easily follows from the definition— T can be drawn using the following procedure: - Reading the first char '(', we put the pen on the paper (marking the root). □ - Reading every next '(', we draw the edge to the next child of the current vertex. - Reading each ')', we return the pen to the parent. In the root, we lift the pen and are finished. □ Petr Hliněný, Fl MU Brno, 2017 31/33 Fl: MA010: What is a Graph The core idea behind the tree isomorphism testing algorithm is to compare their codes which are rooted in the centers and ordered lexicographically among the children. Algorithm 1.20. Testing isomorphism of two trees. input < trees T and U; if (\V(T)\ ^ \V(U)\) return ' Not isomorphic'; □ (T,r) ^— rooted_at_center(T); (U,s) ^— rooted_at_center(U); k 4— minimal_code(T,r); m 4— minimal.code(U,s); if (k = m as strings) return 'Isomorphic.'; else return ' Not isomorphic' ; □ Function minimal_code(tree X, root r) { if (\V(X)\ = 1) return "()"; d <— number of components of X\r, i.e. subtrees of r; foreach (i 4— 1,...,d) { Y[i] <— i-th connected component of X\r; s[i] <— i-th neighbour ofr, i.e. the root of the subtree Y [i] ; k[i] 4— minimal_code (Y [i] , s [i] ) ; > sort as k[l] Petr Hliněný, Fl MU Brno, 2017 32/33 Fl: MA010: What is a Graph ^The proof A mathematical proof of Algorithm 1.20 is given as follows. Theorem 1.21. Let T, U be two trees on the same number of vertices, and let (T", r) and (U',s) be their rooted trees obtained in the first step of Algorithm 1.20 (r,s are the centers ofT, U). Then: a) T and U are isomorphic if, and only if, (X",r) is isomorphic to (U',s). b) (T",r) is isomorphic to (Ufs) if, and only if, minimal_code(T/, r) = minimal_code(U/, s). □ Proof (sketch): Claim (a) immediately follows from the unique choice of a center. □ Claim (b) is proved by induction on the depth of our rooted trees (T",r) and (U',s). If their depths differ, then they are clearly not isomorphic. On the other hand, two rooted trees of depth 0 are always isomorphic with the code '()'. So let (T",r) and (U',s) be both of depth £ > 0. If their codes in the algorithm are identical, then (X",r) and (U',s) are clearly isomorphic. □ Conversely, if (T7, r) and (U', s) are isomorphic, then there exists a "matching" bijection between the subtrees of their roots, and hence the codes of matching subtrees are identical by the inductive assumption. Since the codes of the subtrees are sorted in the same way, we get minimal_code(T7, r) = minimal_code(U/, s). □ Petr Hliněný, Fl MU Brno, 2017 33/33 Fl: MA010: What is a Graph