Semester 6 Discrete Mathematics Lecture 6: n-ary Relations PDF

University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (6): ***n*-ary Relations** Instructor: Prof. Noureldien Abdelrahman **6.1 n-ary Relations** **DEFINITION 1** Let *A*~1~*,A*...

University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (6): ***n*-ary Relations** Instructor: Prof. Noureldien Abdelrahman **6.1 n-ary Relations** **DEFINITION 1** Let *A*~1~*,A*~2~*,... , A~n~* be sets.An *n-ary relation* on these sets is a subset of *A*~1~ × *A*~2~ ×・ ・ ・×*A~n~*. The sets *A*~1~ *,A*~2~*,... , A~n~* are called the ***[domains]*** of the relation, and *n* is called its **[*degree*.]** **EXAMPLE 1** Let *R* be the relation on **N** × **N** × **N** consisting of triples *(a, b, c)*, where *a, b*, and *c* are integers with *a \< b \< c*. Then *(*1*,* 2*,* 3*)* ∈ *R*, but *(*2*,* 4*,* 3*) /*∈ *R*. The degree of this relation is 3. Its domains are all equal to the set of natural numbers. **EXAMPLE 2** Let *R* be the relation on **Z** × **Z** × **Z** consisting of all triples of integers *(a, b, c)* in which *a*, *b*, and *c* form an arithmetic progression. That is, *(a, b, c)* ∈ *R* if and only if there is an integer *k* such that *b* = *a* + *k* and *c* = *a* + 2*k*, or equivalently, such that *b* − *a* = *k* and *c* − *b* = *k*. Note that *(*1*,* 3*,* 5*)* ∈ *R* because 3 = 1 + 2 and 5 = 1 + 2 ・ 2, but *(*2*,* 5*,* 9*) /*∈ *R* because 5 − 2 = 3 while 9 − 5 = 4. This relation has degree 3 and its domains are all equal to the set of integers. **6.2 Databases and Relations** A database consists of **records**, which are *n*-tuples, made up of **fields**. The fields are the entries of **[the *n*-tuples]**. For instance, a database of student records may be made up of fields containing the name, student number, major, and grade point average of the student. **[The relational data model represents a database of records as an *n*-ary relation.]** Thus, student records are represented as **[4-tuples]** of the form (*Student\_name, ID\_number, Major, GPA*). A sample database of six such records is (Ackermann, 231455, Computer Science, 3.88) (Adams, 888323, Physics, 3.45) (Chou, 102147, Computer Science, 3.49) (Goodfriend, 453876, Mathematics, 3.45) (Rao, 678543, Mathematics, 3.90) (Stevens, 786576, Psychology, 2.99). **[Relations used to represent databases are also called tables, because these relations are often displayed as tables.]** Each column of the table corresponds to an *attribute* of the database. For instance, the same database of students is displayed in Table 1. The attributes of this database are Student Name, ID Number, Major, and GPA. **6.3 Operations on *n*-ary Relations** There are a [variety of operations on *n*-ary relations that can be used to form new *n*-ary relations.] Applied together, these operations can answer queries on databases that ask for all *n*-tuples that satisfy certain conditions. [The most basic operation on an *n*-ary relation is determining all *n*-tuples in the *n*-ary relation that satisfy certain conditions]. For example, we may want to find all the records of all computer science majors in a database of student records. We may want to find all students who have a grade point average above 3.5.We may want to find the records of all computer science majors who have a grade point average above 3.5. To perform such tasks we use **[the selection operator]**. **DEFINITION 2 (The Selection Operator)** Let *R* be an *n*-ary relation and ***C*** a condition that elements in *R* may satisfy. Then the ***[selection operator sC]*** maps the *n*-ary relation *R* to the *n*-ary relation of all *n*-tuples from *R* that satisfy the condition *C*. **EXAMPLE 3** To find the records of computer science majors in the *n*-ary relation *R* shown in Table 1, we use the operator **[*sC*1]** , where *C*1 is the condition *Major="Computer Science."* The result is the two 4-tuples (Ackermann, 231455, Computer Science, 3.88) and (Chou, 102147, Computer Science, 3.49). Similarly, to find the records of students who have a grade point average above 3.5 in this database, we use the operator **[*sC*2]** , where *C*2 is the condition *GPA \> 3.5.* The result is the two 4-tuples (Ackermann, 231455, Computer Science, 3.88) and (Rao, 678543, Mathematics, 3.90). Finally, to find the records of computer science majors who have a GPA above 3.5, we use the operator **[*sC*3]** , where *C*3 is the condition *(Major="Computer Science" ∧ GPA \> 3.5).* The result consists of the single 4-tuple (Ackermann, 231455, Computer Science, 3.88). **6.3.1 The Projection Operator** In other words, the projection *Pi*~1~*,i*~2~*,\...,i~m~* deletes *n* − *m* of the components of an *n*-tuple, leaving the *i*~1~th, *i*~2~th*,... ,* and *i~m~*th components. **EXAMPLE 4** What results when the projection *P*1*,*3 is applied to the 4-tuples *(*2*,* 3*,* 0*,* 4*),* (Jane Doe, 234111001, Geography, 3.14), and *(a*1*, a*2*, a*3*, a*4*)*? ***Solution:*** The projection *P*1*,*3 sends these 4-tuples to *(*2*,* 0*)*, (Jane Doe, Geography), and *(a*1*, a*3*)*, respectively. **EXAMPLE 5** What relation results when the projection ***P*1*,*4** is applied to the relation in **Table 1**? *Solution:* When the projection *P*1*,*4 is used, [the second and third columns of the table are deleted,] and pairs representing student names and grade point averages are obtained. **EXAMPLE 6** What is the table obtained when the projection *P*1*,*2 is applied to the relation in Table 3? ***Solution*** [The same table but with only one column, The first and the second columns are deleted.] **6.3.2 The Join Operator** The **join** operation is used to combine two tables into one when these tables share some identical fields. For instance, a table containing fields for airline, flight number, and gate, and another table containing fields for flight number, gate, and departure time can be combined into a table containing fields for airline, flight number, gate, and departure time. In other words, the **join operator *Jp*** produces a new relation from two relations by combining all *m*-tuples of the first relation with all *n*-tuples of the second relation, where the **last *p* components** of the *m*-tuples agree with the **first *p* components** of the *n*-tuples. **EXAMPLE 7** What relation results when the join **operator *J*2** is used to combine the relation displayed in Tables 5 and 6? *Solution:* The join *J*2 produces the relation shown in Table 7. **6.4 SQL** The database query language SQL (short for Structured Query Language) can be used to carry out the operations we have described in this section. Example 8 illustrates how SQL commands are related to operations on *n*-ary relations. **EXAMPLE 8** We will illustrate how SQL is used to express queries by showing how SQL can be employed to to make a query about airline flights using Table 8. The SQL statement SELECT Departure\_time FROM Flights WHERE Destination='Detroit' is used to find the **projection *P*5** (on the Departure\_time attribute) of the selection of 5-tuples in the Flights database that satisfy the condition*: Destination='Detroit'*. The output would be a list containing the times of flights that have Detroit as their destination, namely, 08:10, 08:47, and 09:44. SQL uses the FROM clause to identify the *n*-ary relation the query is applied to, the WHERE clause to specify the condition of the selection operation, and the SELECT clause to specify the projection operation that is to be applied. (*Beware:* SQL uses SELECT to represent a projection, rather than a selection operation. This is an unfortunate example of conflicting terminology.) University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (7): **Representing Relations** Instructor: Prof. Noureldien Abdelrahman **2.1 Introduction** There are many ways to represent a relation between finite sets. As we have seen one way is to list its ordered pairs. Another way to represent a relation is to use a table. In this section we will discuss two alternative methods for representing relations. One method uses zero--one matrices. The other method uses pictorial representations called directed graphs, which we will discuss later in this section. Generally, matrices are appropriate for the representation of relations in computer programs. On the other hand, people often find the representation of relations using directed graphs useful for understanding the properties of these relations. **7.2 Representing Relations Using Matrices** A relation between finite sets can be represented using a zero--one matrix. Suppose that *R* is a relation from *A* = {*a*~1~*, a*~2~*,... , a~m~*} to *B* = {*b*~1~*, b*~2~*,... , b~n~*}. The relation *R* can be represented by the matrix **M***R* = \[*m~ij~* \], where In other words, the zero--one matrix [representing *R* has a 1 as its *(i, j )* entry when *a~i~* is related to *b~j~*, and a 0 in this position if *a~i~* is not related to *b~j~*]. (Such a representation depends on the orderings used for *A* and *B*.) The use of matrices to represent relations is illustrated in Examples 1--6. **EXAMPLE 1** Suppose that *A* = {1*,* 2*,* 3} and *B* = {1*,* 2}. Let *R* be the relation from *A* to *B* containing *(a, b)* if *a* ∈ *A*, *b* ∈ *B*, and *a \> b*. What is the matrix representing *R* if *a*~1~ = 1, *a*~2~ = 2, and *a*~3~ = 3, and *b*~1~ = 1 and *b*~2~ = 2? ***Solution:*** Because *R* = {*(*2*,* 1*), (*3*,* 1*), (*3*,* 2*)*}, the matrix for *R* is ⎦*.* The 1s in **M***~R~* show that the pairs *(*2*,* 1*)*, *(*3*,* 1*)*, and *(*3*,* 2*)* belong to *R*. The 0s show that no other pairs belong to *R*. **EXAMPLE 2** Let *A* = {*a*~1~*, a*~2~*, a*~3~} and *B* = {*b*~1~*, b*~2~*, b*~3~*, b*~4~*, b*~5~}. Which ordered pairs are in the relation *R* represented by the matrix *Solution:* Because *R* consists of those ordered pairs *(a~i~, b~j~ )* with *m~ij~* = 1, it follows that *R* = {*(a*~1~*, b*~2~*), (a*~2~*, b*~1~*), (a*~2~*, b*~3~*), (a*~2~*, b*~4~*), (a*~3~*, b*~1~*), (a*~3~*, b*~3~*), (a*~3~*, b*~5~*)*}*.* The matrix of a relation on a set, which is a square matrix, can be used to determine whether the relation has certain properties. Recall that a relation *R* on *A* is reflexive if *(a, a)* ∈ *R* whenever *a* ∈ *A*. Thus, *R* is reflexive if and only if *(a~i~, a~i~)* ∈ *R* for *i* = 1*,* 2*,... , n*. Hence, *R* is reflexive if and only if *m~ii~* = 1, for *i* = 1*,* 2*,... , n*. In other words, *R* is reflexive if all the elements on the main diagonal of **M***R* are equal to 1, as shown in Figure 1. Note that the elements off the main diagonal can be either 0 or 1. [The relation *R* is symmetric if *(a, b)* ∈] *R* implies that *(b, a)* ∈ *R*. Consequently, the relation *R* on the set *A* = {*a*1*, a*2*,... , an*} is symmetric if and only if *(aj, ai)* ∈ *R* whenever *(a~i~, a~j~ )* ∈ *R*. In terms of the entries of **M***R*, *R* is symmetric if and only if *m~ji~* = 1 whenever *m~ij~* = 1. This also means *m~ji~* = 0 whenever *m~ij~* = 0. Consequently, *R* is symmetric if and only if *m~ij~* = *m~ji~* , for all pairs of integers *i* and *j* with *i* = 1*,* 2*,... , n* and *j* = 1*,* 2*,... , n*. that is, if **M***~R~* is a symmetric matrix. The form of the matrix for a symmetric relation is illustrated in Figure 2(a). The relation *R* is [antisymmetric if and only if *(a, b)* ∈ *R* and *(b, a)* ∈ *R* imply that *a* = *b*.] Consequently, the matrix of an antisymmetric relation has the property that if *m~ij~* = 1 with *i≠* *j* , then *m~ji~* = 0. Or, in other words, either *m~ij~* = 0 or *m~ji~* = 0 when *i* ≠ *j*. The form of the matrix for an antisymmetric relation is illustrated in Figure 2(b). **EXAMPLE 3** Suppose that the relation *R* on a set is represented by the matrix Is *R* reflexive, symmetric, and/or antisymmetric? *Solution:* Because all the diagonal elements of this matrix are equal to 1, *R* is reflexive. Moreover, because **M***~R~* is symmetric, it follows that *R* is symmetric. It is also easy to see that *R* is not antisymmetric. **7.3 Boolean Operations** Suppose that *R*~1~ and *R*~2~ are relations on a set *A* represented by the matrices **M**~*R*1~ and **M**~*R*2~ , respectively. The matrix representing the union of these relations has a 1 in the positions where either **M**~*R*1~ or **M**~*R*2~ has a 1. The matrix representing the intersection of these relations has a 1 in the positions where both **M**~*R*1~ and **M**~*R*2~ have a 1. Thus, the matrices representing the union and intersection of these relations are **7.4 Matrix of Composite Relations** In particular, suppose that *R* is a relation from *A* to *B* and *S* is a relation from *B* to *C*. Suppose that *A*, *B*, and *C* have *m*, *n*, and *p* elements, respectively. Let the zero-- one matrices for *S* ◦*R*, *R*, and *S* be **M**~*S*\ ◦*R*~ = \[*t~ij~* \], **M***~R~* = \[*r~ij~* \], and **M***~S~* = \[*s~ij~* \], respectively (these matrices have sizes *m* × *p*, *m* × *n*, and *n* × *p*, respectively). The ordered pair *(a~i~, c~j~ )* belongs to *S* ◦*R* if and only if there is an element *bk* such that *(ai, b~k~)* belongs to *R* and *(b~k~, c~j~ )* belongs to *S*. It follows that *t~ij~* = 1 if and only if *r~ik~* = *s~kj~* = 1 for some *k*. From the definition of the Boolean product, this means that **7.5 Representing Relations Using Digraphs** **DEFINITION 1** A *directed graph*, or *digraph*, consists of a set *V* of *vertices* (or *nodes*) together with a set *E* of ordered pairs of elements of *V* called *edges* (or *arcs*). The vertex *a* is called the *initial vertex* of the edge *(a, b)*, and the vertex *b* is called the *terminal vertex* of this edge. An edge of the form *(a, a)* is represented using an arc from the vertex *a* back to itself. Such an edge is called a **loop**. **EXAMPLE 6** The directed graph with vertices *a*, *b*, *c*, and *d*, and edges *(a, b)*, *(a, d)*, *(b, b)*, *(b, d)*, *(c, a)*, *(c, b)*, and *(d, b)* is displayed in Figure 3. **EXAMPLE 7** The directed graph of the relation *R* = {*(*1*,* 1*), (*1*,* 3*), (*2*,* 1*), (*2*,* 3*), (*2*,* 4*), (*3*,* 1*), (*3*,* 2*), (*4*,* 1*)*} on the set {1*,* 2*,* 3*,* 4} is shown in Figure 4. **EXAMPLE 8** What are the ordered pairs in the relation *R* represented by the directed graph shown in Figure 5? *Solution:* The ordered pairs *(x, y)* in the relation are *R* = {*(*1*,* 3*), (*1*,* 4*), (*2*,* 1*), (*2*,* 2*), (*2*,* 3*), (*3*,* 1*), (*3*,* 3*), (*4*,* 1*), (*4*,* 3*)*}*.* Each of these pairs corresponds to an edge of the directed graph, with *(*2*,* 2*)* and *(*3*,* 3*)* corresponding to loops. University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (8): **Graphs and Graph Models** Instructor: Prof. Noureldien Abdelrahman **8.1 Introduction** **DEFINITION 1** A *graph G* = *(V ,E)* [consists of *V* , a nonempty set of *vertices* (or *nodes*) and *E*, a set of *edges*.] Each edge has either one or two vertices associated with it, called its *endpoints*. An edge is said to *connect* its endpoints. [A graph in which each edge connects two different vertices and where] [no two edges connect the same pair of vertices is called a **simple graph**]. Note that in a simple graph, each edge is associated to an unordered pair of vertices, and no other edge is associated to this same edge. A computer network may contain multiple links between data centers, as shown in Figure 2. To model such networks, we need graphs that have more than one edge connecting the same pair of vertices. [Graphs that may have **multiple edges** connecting the same vertices are called **multigraphs**]. When there are *m* different edges associated to the same unordered pair of vertices {*u, v*}, we also say that {*u, v*} is an edge of multiplicity *m*. That is, we can think of this set of edges as *m* different copies of an edge {*u, v*}. [So far the graphs we have introduced are **undirected**] **graphs**. Their edges are also said to be **undirected**. However, to construct a graph model, we may find it necessary to assign directions to the edges of a graph. For example, in a computer network, some links may operate in only one direction (such links are called single duplex lines). This may be the case if there is a large amount of traffic sent to some data centers, with little or no traffic going in the opposite direction. **EFINITION 2** [A *directed graph* (or *digraph*) *(V ,E)* consists of a nonempty set of vertices *V* and a set of *directed edges* (or *arcs*) *E*.] Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (*u, v*) is said [to *start* at *u* and *end* at *v*.] When a directed [graph has no loops and has no multiple directed edges], it is [called a **simple directed graph**]. In some computer networks, multiple communication links between two data centers may be present. Directed graphs that may have **multiple directed edges** from a vertex to a second (possibly the same) vertex are used to model such networks. We called [such graphs **directed multigraphs**]. When there are *m* directed edges, each associated to an ordered pair of vertices *(u, v)*, we say that *(u, v)* is an edge of **multiplicity** *m*. **DEFINITION 3** Two vertices *u* and *v* in an undirected graph [*G* are called *adjacent*] (or *neighbors*) in *G* if *u* [and *v* are endpoints of an edge *e* of] *G*. Such an edge *e* is [called *incident*] *with* [the vertices *u* and *v* and] *e* is said to *connect u* and *v*. **DEFINITION 4** The [*degree of a vertex in an undirected graph* is the number of edges incident with it,] except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex *v* is denoted by deg*(v)*. **THEOREM 1** Let *G* = *(V, E)* be an undirected graph with *m* edges. Then **EXAMPLE 1** How many edges are there in a graph with 10 vertices each of degree six? ***Solution:*** Because the sum of the degrees of the vertices is 6 ・ 10 = 60, it follows that 2*m* = 60 where *m* is the number of edges. Therefore, *m* = 30. Theorem 1 shows that the sum of the degrees of the vertices of an undirected graph is even. This simple fact has many consequences, one of which is given as Theorem 2. **THEOREM 2** An undirected graph has an even number of vertices of odd degree. ***Proof:*** Let *V*1 and *V*2 be the set of vertices of even degree and the set of vertices of odd degree, respectively, in an undirected graph *G* = *(V ,E)* with *m* edges. Then Since summation of degrees V1 is even then the Summation of degrees of V2 is also even, thus V2 must be even. **DEFINITION 4** When *(u, v)* is an edge of the graph *G* with directed edges, [*u* is said to be *adjacent to v* and *v* is said to be *adjacent from u*]. The vertex [*u* is called the *initial vertex* of *(u, v)*, and *v* is called the *terminal* or *end vertex* o]f *(u, v)*. The initial vertex and terminal vertex of a loop are the same. **DEFINITION 5** In a graph with directed edges the [*in-degree of a vertex v*,] denoted by deg−*(v)*, is the [number of edges with *v* as their terminal vertex]. The *out-degree of v*, denoted by deg+ *(v)*, is the number of edges with *v* as their initial vertex. **EXAMPLE 2** In Figure 2, find the deg- and deg+ for all vertices. ***Solution:*** The in-degrees in *G* are deg−*(a)* = 2, deg−*(b)* = 2, deg−*(c)* = 3, deg−*(d)* = 2,deg−*(e)* = 3, and deg−*(f )* = 0. The out-degrees are deg+*(a)* = 4, deg+*(b)* = 1, deg+*(c)* = 2, deg+ *(d)* = 2, deg+ *(e)* = 3, and deg+*(f )* = 0. Because each edge has an initial vertex and a terminal vertex, the sum of the in-degrees and the sum of the out-degrees of all vertices in a graph with directed edges are the same. Both of these sums are the number of edges in the graph. This result is stated as Theorem 3. **THEOREM 3** Let *G* = *(V ,E)* be a graph with directed edges. Then There are many properties of a graph with directed edges that do not depend on the direction of its edges. Consequently, it is often useful to ignore these directions. The undirected graph that results [from ignoring directions of edges is called the **underlying undirected graph**]. A graph with directed edges and its underlying undirected graph have the same number of edges. **8.2 Some Special Simple Graphs** We will now introduce several classes of simple graphs. These graphs are often used as examples and arise in many applications **1. Complete Graphs** [A **complete graph on *n* vertices**], denoted by *K~n~*, is a simple graph that contains exactly one edge between each pair of distinct vertices. The graphs *K~n~*, for *n* = 1*,* 2*,* 3*,* 4*,* 5*,* 6, are displayed in Figure 3. A simple graph for which there is at least one pair of distinct vertex not connected by an edge is called **noncomplete**. **2. Cycles Graphs** A **cycle *C~n~***, *n* ≥ 3, consists of *n* vertices *v*~1~*, v*~2~*,... , v~n~* and edges {*v*~1~*, v*~2~}, {*v*~2~*, v*~3~}*,... ,* {*v~n~*~−1~*, v~n~*}, and {*v~n~, v*~1~}. The cycles *C*3, *C*4, *C*5, and *C*6 are displayed in Figure 4. **3. Bipartite Graphs** Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets such that each edge connects a vertex in one of these subsets to a vertex in the other subset. **DEFINITION 6** A simple graph *G* is called *bipartite* if its vertex set *V* can be partitioned into two disjoint sets *V*~1~ and *V*~2~ such that every edge in the graph connects a vertex in *V*~1~ and a vertex in *V*~2~ (so that no edge in *G* connects either two vertices in *V*~1~ or two vertices in *V*~2~). When this condition holds, we call the pair *(V*~1~*, V*~2~*)* a *bipartition* of the vertex set *V* of *G*. **EXAMPLE 3** *C*~6~ is bipartite, as shown in Figure 7, because its vertex set can be partitioned into the two sets *V*~1~ = {*v*~1~*, v*~3~*, v*~5~} and *V*~2~ = {*v*~2~*, v*~4~*, v*~6~}, and every edge of *C*~6~ connects a vertex in *V*~1~ and a vertex in *V*~2~. **EXAMPLE 4** *K*3 is not bipartite. To verify this, note that if we divide the vertex set of *K*3 into two disjoint sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices could not be connected by an edge, but in *K*3 each vertex is connected to every other vertex by an edge. **EXAMPLE 5** Are the graphs *G* and *H* displayed in Figure 8 bipartite? *Solution:* Graph *G* is bipartite because its vertex set is the union of two disjoint sets, **{*a, b, d*}** and **{*c, e, f, g*},** and each edge connects a vertex in one of these subsets to a vertex in the other subset. Graph *H* is not bipartite because its vertex set cannot be partitioned into two subsets so that edges do not connect two vertices from the same subset. **EXAMPLE 6** **Complete Bipartite Graphs:** A **complete bipartite graph *K~m~,~n~*** is a graph that has its vertex set partitioned into two subsets of *m* and *n* vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. The complete bipartite graphs *K*~2*,*3~, *K*~3*,*3~, *K*~3*,*5~, and *K*~2*,*6~ are displayed in Figure 9. **8.3 Bipartite Graphs and Matching** Bipartite graphs can be used to model many types of applications that involve matching the elements of one set to elements of another, as Example 7 illustrates. **EXAMPLE 7** **Job Assignments:** Suppose that there are *m* employees in a group and *n* different jobs that need to be done, where *m* ≥ *n*. Each employee is trained to do one or more of these *n* jobs. We would like to assign an employee to each job. To help with this task, we can use a graph to model employee capabilities. We represent each employee by a vertex and each job by a vertex. For each employee, we include an edge from that employee to all jobs that the employee has been trained to do. Note that the vertex set of this graph can be partitioned into two disjoint sets, the set of employees and the set of jobs, and each edge connects an employee to a job. Consequently, this graph is bipartite, where the bipartition is *(E, J )* where *E* is the set of employees and *J* is the set of jobs. **8.4 Subgraphs** **DEFINITION 7** A *subgraph of a graph G* = *(V ,E)* is a graph *H* = *(W, F)*, where *W* ⊆ *V* and *F* ⊆ *E*. A subgraph *H* of *G* is a *proper subgraph* of *G* if *H* = *G*. Given a set of vertices of a graph, we can form a subgraph of this graph with these vertices and the edges of the graph that connect them. **DEFINITION 8** Let *G* = *(V ,E)* be a simple graph. The **subgraph induced** by a subset *W* of the vertex set *V* is the graph *(W, F)*, where the edge set *F* contains an edge in *E* if and only if both endpoints of this edge are in *W*. **EXAMPLE 8** The graph *G* shown in Figure 15 is a subgraph of *K*5. If we add the edge connecting *c* and *e* to *G*, we obtain the subgraph induced by *W* = {*a, b, c, e*}. **8.5 REMOVING OR ADDING EDGES OF A GRAPH** Given a graph *G* = *(V ,E)* and an edge *e* ∈ *E*, we can **[produce a subgraph of *G* by removing the edge *e*]**. The resulting subgraph, denoted by *G* − *e*, has the same vertex set *V* as *G*. Its edge set is *E* − *e*. Hence, *G* − *e* = *(V ,E* − {*e*}*).* Similarly, if *E'* is a subset of *E*, we can produce a subgraph of *G* by removing the edges in *E'* from the graph. The resulting subgraph has the same vertex set *V* as *G*. Its edge set is *E* -- *E'*. **8.6 REMOVING VERTICES FROM A GRAPH** When we remove a vertex *v* and all edges incident to it from *G* = *(V ,E)*, we produce a **[subgraph, denoted by *G* −]** *v*. Observe that *G* − *v* = *(V* − *v, E')*, where *E'* is the set of edges of *G* not incident to *v*. Similarly, if *V'* is a subset of *V*, then the graph *G* -- *V'* is the subgraph *(V* -- *V',E' )*, where *E'* is the set of Edges of *G* not incident to a vertex in *V'*. **8.7 GRAPH UNIONS** Two or more graphs can be combined in various ways. The new graph that contains all the vertices and edges of these graphs is called the **union** of the graphs. We will give a more formal definition for the union of two simple graphs. **DEFINITION 9** The *union* of two simple graphs *G*1 = *(V*1*,E*1*)* and *G*2 = *(V*2*,E*2*)* is the simple graph with vertex set *V*1 ∪ *V*2 and edge set *E*1 ∪ *E*2. The union of *G*1 and *G*2 is denoted by *G*1 ∪ *G*2. **EXAMPLE 9** Find the union of the graphs *G*1 and *G*2 shown in Figure 16(a). ***Solution:*** The vertex set of the union *G*1 ∪ *G*2 is the union of the two vertex sets, namely, {*a, b, c, d, e, f* }. The edge set of the union is the union of the two edge sets. The union is displayed in Figure 16(b). University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (9): **Graphs Representation** Instructor: Prof. Noureldien Abdelrahman **9.1 Adjacency Matrices** Two types of matrices commonly used to represent graphs will be presented here. One is based on the **[adjacency of vertices]**, and the other is based on **[incidence of vertices and edges.]** Vertices of *G* are listed arbitrarily as *v*~1~*, v*~2~*,... , v~n~*. The **adjacency matrix A** (or **A***G*) of *G*, with respect to this listing of the vertices, is the *n* x *n* [zero--one matrix] with 1 as its *(i, j )*^th^ entry when *v~i~* and *v~j~* are adjacent, and 0 as its *(i, j )*^th^ entry when they are not adjacent. In other words, if its adjacency matrix is **A** = \[*a~ij~* \], then **EXAMPLE 1** Use an adjacency matrix to represent the graph shown in Figure 3. **Solution:** We order the vertices as *a, b, c, d as rows and columns*. The matrix representing this graph is **EXAMPLE 2** Draw a graph with the adjacency matrix with respect to the ordering of vertices *a, b, c, d*. ***Solution:*** A graph with this adjacency matrix is shown in Figure 4. **EXAMPLE 3** Use an adjacency matrix to represent the pseudograph shown in Figure 5. ***Solution:*** The adjacency matrix using the ordering of vertices *a, b, c, d* is **9.2 Incidence Matrices** Another common way to represent graphs is to use **incidence matrices**. Let *G* = *(V ,E)* be an undirected graph. Suppose that *v*~1~*, v*~2~*,... , v~n~* are the vertices and *e*~1~*, e*~2~*,... , e~m~* are the edges of *G*. Then the incidence matrix with respect to this ordering of *V* and *E* is the *n* × *m* matrix **M** = \[*m~ij~* \], where **EXAMPLE 4** Represent the graph shown in Figure 6 with an incidence matrix. ***Solution:*** The incidence matrix is **9.3 Isomorphism of Graphs** We often need to know whether two graphs that have different shapes represent the same graph or not. Graphs that have different shapes but represent the same graph are called isomorphic graphs. **DEFINITION 1** The simple graphs *G*1 = *(V*1*, E*1*)* and *G*2 = *(V*2*, E*2*)* are *isomorphic* if there exists a one to- one and onto function *f* from *V*1 to *V*2 with the property that *a* and *b* are adjacent in *G*1 if and only if *f (a)* and *f (b)* are adjacent in*G*2, for all *a* and *b* in *V*1. Such a function *f* is called an *isomorphism*. Two simple graphs that are not isomorphic are called *nonisomorphic*. **EXAMPLE 5** Show that the graphs *G* = *(V, E)* and *H* = *(W, F)*, displayed in Figure 8, are isomorphic. ***Solution*** The function *f* with *f (u*1*)* = *v*1, *f (u*2*)* = *v*4, *f (u*3*)* = *v*3, and *f (u*4*)* = *v*2 is a one to-one correspondence between *V* and *W*. To see that this correspondence preserves adjacency, note that adjacent vertices in *G* are *u*1 and *u*2*, u*1 and *u*3, *u*2 and *u*4, and *u*3 and *u*4, and each of the pairs *f (u*1*)* = *v*1 and *f (u*2*)* = *v*4, *f (u*1*)* = *v*1 and *f (u*3*)* = *v*3, *f (u*2*)* = *v*4 and *f (u*4*)* = *v*2, and *f (u*3*)* = *v*3 and *f (u*4*)* = *v*2 consists of two adjacent vertices in *H*. **Determining Whether Two Simple Graphs Are Isomorphic** It is often difficult to determine whether two simple graphs are isomorphic. There are *n*! possible one-to-one correspondences between the vertex sets of two simple graphs with *n* vertices. Testing each such correspondence to see whether it preserves adjacency is impractical if *n* is large. Sometimes it is not hard to show that two graphs are not isomorphic. [In particular, we can show that two graphs are not isomorphic if we can find a property only one of the two graphs has, but that is not preserved by isomorphis]m. A property preserved by isomorphism of graphs is called a **graph invariant**. For instance, isomorphic simple graphs must have - the same number of vertices - the same number of edges - the same vertices degrees **EXAMPLE 6** Show that the graphs displayed in Figure 9 are not isomorphic. ***Solution:*** Both *G* and *H* have five vertices and six edges. However, *H* has a vertex of degree one, namely, *e*, whereas *G* has no vertices of degree one. It follows that *G* and *H* are not isomorphic. The number of vertices, the number of edges, and the number of degrees of vertices are all invariants under isomorphism. If any of these quantities differ in two simple graphs, these graphs cannot be isomorphic. [However, when these invariants are the same, it does not necessarily mean that the two graphs are isomorphic]. **EXAMPLE 7** Determine whether the graphs shown in Figure 10 are isomorphic. ***Solution:*** The graphs *G* and *H* both have eight vertices and 10 edges, and also both have four vertices of degree two and four of degree three, but it is still conceivable that these graphs are not isomorphic. However, *G* and *H* are not isomorphic. To see this, note that because deg*(a)* = 2 in *G*, *a* must correspond to either *t* , *u*, *x*, or *y* in *H*, because these are the vertices of degree two in *H*. However, each of these four vertices in *H* is adjacent to another vertex of degree two in *H*, which is not true for *a* in *G*. University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (10): **Adjacency Matrices Connectivity** Instructor: Prof. Noureldien Abdelrahman **10.1 Introduction** Many problems can be [modeled with paths formed] by traveling along the edges of graphs. For instance, the problem of determining whether a message can be sent between two computers using intermediate links can be studied with a graph model. Problems of efficiently planning routes for mail delivery, garbage pickup, diagnostics in computer networks, and so on can be solved using models that involve paths in graphs. **Paths** Informally, a **path** is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph. As the path travels along its edges, it visits the vertices along this path, that is, the endpoints of these edges. A formal definition of paths and related terminology is given in Definition 1. **DEFINITION 1** Let *n* be a nonnegative integer and *G* an undirected graph. A *path* of *length n* from *u* to *v* in *G* is a sequence of *n* edges *e*~1~*,... , e~n~* of *G* for which there exists a sequence *x*~0~ = *u, x*~1~*,... , x~n~*~−1~*, x~n~* = *v* of vertices such that *e~i~* has, for *i* = 1*,... , n*, the endpoints *x~i~*~−1~ and *x~i~*. When the graph is simple, we denote this path by its vertex sequence *x*~0~*, x*~1~*,... , x~n~* (because listing these vertices uniquely determines the path). The path [is a *circuit* if it begins and ends at the same vertex], that is, if *u* = *v*, and has length greater than zero. The path or circuit is said to *pass through* the vertices *x*~1~*, x*~2~*,... , x~n~*~−1~ or *traverse* the edges *e*~1~*, e*~2~*,... , e~n~*. A path or circuit is *simple* if it does not contain the same edge more than once. **EXAMPLE 1** In the simple graph shown in Figure 1, *a*, *d*, *c*, *f* , *e* is a simple path of length 4, because {*a, d*}, {*d, c*}, {*c, f* }, and {*f, e*} are all edges. However, *d*, *e*, *c*, *a* is not a path, because {*e, c*} is not an edge. Note that *b*, *c*, *f* , *e*, *b* is a circuit of length 4 because {*b, c*}, {*c, f* }, {*f, e*}, and {*e, b*} are edges, and this path begins and ends at *b*. The path *a*, *b*, *e*, *d*, *a*, *b*, which is of length 5, is not simple because it contains the edge {*a, b*} twice. **10.2 Euler Paths and Circuits** **DEFINITION 2** An *Euler circuit* in a graph *G* is a simple circuit containing every edge of *G*. An *Euler path* in *G* is a simple path containing every edge of *G*. Examples 2 and 3 illustrate the concept of Euler circuits and paths. **EXAMPLE 2** Which of the undirected graphs in Figure 3 have an Euler circuit, and which do not have, and which have an Euler path? ***Solution:*** The graph *G*1 has an Euler circuit, for example, *a, e, c, d, e, b, a*. Neither of the graphs *G*2 or *G*3 has an Euler circuit (the reader should verify this). However, *G*3 has an Euler path, namely, *a, c, d, e, b, d, a, b*. *G*2 does not have an Euler path (as the reader should verify). **EXAMPLE 3** Which of the directed graphs in Figure 4 have an Euler circuit? Of those that do not, which have an Euler path? ***Solution:*** The graph *H*2 has an Euler circuit, for example, *a, g, c, b, g, e, d, f, a*. Neither *H*1 nor *H*3 has an Euler circuit (as the reader should verify). *H*3 has an Euler path, namely, *c, a, b, c, d, b*, but *H*1 does not (as the reader should verify). **THEOREM 1** A connected graph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. **THEOREM 2** A connected graph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree. **EXAMPLE 4** Which graphs shown in Figure 7 have an Euler path? ***Solution:*** *G*1 contains exactly two vertices of odd degree, namely, *b* and *d*. Hence, it has an Euler path that must have *b* and *d* as its endpoints. One such Euler path is *d, a, b, c, d, b*. Similarly, *G*2 has exactly two vertices of odd degree, namely, *b* and *d*. So it has an Euler path that must have *b* and *d* as endpoints. One such Euler path is *b, a, g, f, e, d, c, g, b, c, f, d*. *G*3 has no Euler path because it has six vertices of odd degree. **10.3 Hamilton Paths and Circuits** **DEFINITION 2** [A simple path in a graph *G* that passes through every vertex exactly once is called a *Hamilton path*,] and a simple [circuit in a graph *G* that passes through every vertex exactly once is called a *Hamilton circuit*]. That is, the simple path *x*~0~*, x*~1~*,... , x~n~*~−1~*, x~n~* in the graph *G* = *(V ,E)* is a Hamilton path if *V* = {*x*~0~*, x*~1~*,... , x~n~*~−1~*, x~n~*} and *x~i~* = *x~j~* for 0 ≤ *i \< j* ≤ *n*, and the simple circuit *x*~0~*, x*~1~*,... , x~n~*~−1~*, x~n~, x*~0~ (with *n \>* 0) is a Hamilton circuit if *x*~0~*, x*~1~*,... , x~n~*~−1~*, x~n~* is a Hamilton path. **EXAMPLE 5** Which of the simple graphs in Figure 10 have a Hamilton circuit or, if not, a Hamilton path? ***Solution:*** *G*1 has a Hamilton circuit: *a, b, c, d, e, a*. There is no Hamilton circuit in *G*2 (this can be seen by noting that any circuit containing every vertex must contain the edge {*a, b*} twice), but *G*2 does have a Hamilton path, namely, *a, b, c, d*. *G*3 has neither a Hamilton circuit nor a Hamilton path, because any path containing all vertices must contain one of the edges {*a, b*}, {*e, f* }, and {*c, d*} more than once.