![]() CATEGORIES: BiologyChemistryConstructionCultureEcologyEconomyElectronicsFinanceGeographyHistoryInformaticsLawMathematicsMechanicsMedicineOtherPedagogyPhilosophyPhysicsPolicyPsychologySociologySportTourism |
Some special simple graphsA partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice. Example. Determine whether the posets represented by each of the Hasse diagrams in Figure below are lattices.
Solution: The posets represented by the Hasse diagrams in (a) and (c) are both lattices because in each poset every pair of elements has both a least upper bound and a greatest lower bound. On the other hand, the poset with the Hasse diagram shown in (b) is not a lattice, since the elements b and c have no least upper bound. To see this note that each of the elements d, e and f is an upper bound, but none of these three elements precedes the other two with respect to the ordering of this poset. Glossary equivalence relation – отношение эквивалентности; partition – разбиение partial order – частичный порядок; linear order – линейный порядок well-ordered set – вполне упорядоченное множество; bound – граница lattice – решетка
Graphs We will introduce the different types of graphs by showing how each can be used to model a computer network. Suppose that a network is made up of computers and telephone lines between computers. We can represent the location of each computer by a point and each telephone line by an arc, as shown in Figure below. There is at most one telephone line between two computers in this network, each line operates in both directions, and no computer has a telephone line to itself. Consequently, this network can be modeled using a simple graph, consisting of vertices that represent the computers and undirected edges that represent telephone lines, where each edge connects two distinct vertices and no two edges connect the same pair of vertices. A simple graph Sometimes there are multiple telephone lines between computers in a network. This is the case when there is a heavy traffic between computers. A network with multiple lines is displayed in Figure below. Simple graphs are not sufficient to model such networks. Instead, multigraphs are used, which consists of vertices and undirected edges between these vertices, with multiple edges between vertices allowed. Every simple graph is also a multigraph. However, not all multigraphs are simple graphs, since in multigraph two or more edges may connect the same pair of vertices. A multigraph A computer network may connect a telephone line from a computer to itself (perhaps for diagnostic purposes). Such a network is shown in Figure below. We cannot use multigraphs to model such networks, since loops, which are edges from a vertex to itself, are not allowed in multigraphs. Instead, pseudographs are used. A pseudograph The telephone lines in a computer network may not operate in both directions. For instance, in Figure below the host computer in New York can only receive data from other computers and cannot send out data. The other telephone lines operate in both directions and are represented by pairs of edges in opposite directions. A directed graph Finally, multiple lines may be present in the computer network, so that there may be several one-way lines to the host in New York from each location, and perhaps more than one line back to each remote computer from the host. A directed multigraph Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if {u, v} is an edge of G. If e = {u, v}, the edge e is called incident with the vertices u and v. The edge e is also said to connect u and v. The vertices u and v are called endpoints of the edge {u, v}. 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). Example. What are the degrees of the vertices in the graph G and H?
Solution: In G, deg(a) = 2, deg(b) = deg(c) = deg(f) = 4, deg(d) = 1, deg(e) = 3 and deg(g) = 0. In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1 and deg(d) = 5. A vertex of degree 0 is called isolated. A vertex is pendant iff it has degree 1. What do we get when we add the degrees of all the vertices of a graph Theorem 1 (The Handshaking Theorem). Let Example. How many edges are there in a graph with 10 vertices each of degree 6? Solution: Since the sum of the degrees of the vertices is Theorem 2. An undirected graph has an even number of vertices of odd degree. Proof: Let V1 and V2 be the set of vertices of even degree and the set of vertices of odd degree, respectively, in an undirected graph 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 of (u, v). The initial vertex and terminal vertex of a loop are the same. In a graph with directed edges the in-degree of a vertex v, denoted by Example. Find the in-degree and out-degree of each vertex in the graph G with directed edges. Solution:
Since 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 the following theorem. Theorem 3. Let
Some special simple graphs Example. The complete graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices.
Example. The cycle
Example. We obtain the wheel Wn when we add an additional vertex to the cycle Cn, for
Example. The n-cube, denoted by Qn, is the graph that has vertices representing the 2n bit strings of length n. Two vertices are adjacent iff the bit strings that they represent differ in exactly one bit position.
Date: 2015-01-02; view: 3955
|