Graphs
some cool online notes
The word "graph" has (at least) two meanings in mathematics.
In elementary mathematics, "graph" refers to a function graph or "graph of a function," i.e., a plot.
In a mathematician's terminology, a graph is a collection of points and lines connecting some (possibly empty) subset of them. The points of a graph are most commonly known as graph vertices, but may also be called "nodes" or simply "points." Similarly, the lines connecting the vertices of a graph are most commonly known as graph edges, but may also be called "arcs" or "lines."
The study of graphs is known as graph theory, and was first systematically investigated by D. König in the 1930s (Gardner 1984, p. 91). Unfortunately, as Gardner (1984, p. 91) notes, "The confusion of this term [i.e., the term "graph" to describe a network of vertices and edges] with the 'graphs' of analytic geometry [i.e., plots of functions] is regrettable, but the term has stuck." Some educators use the term "vertex-edge graph" for a connected set of nodes in an attempt to preserve the common usage of "graph" to mean the plot of a function.
Euler's proof of the nonexistence of a so-called Eulerian cyclecross all seven bridges of Königsberg, now known as the Königsberg bridge problem, is a famous precursor to graph theory. In fact, the study of various sorts of paths in graphs (e.g., Eulerian paths, Eulerian cycles, Hamiltonian paths, and Hamiltonian cycles) has many applications in real-world problems.
Graphs come in a wide variety of different sorts. The most common type is graphs in which at most one edge (i.e., either one edge or no edges) may connect any two vertices. Such graphs are called simple graphs. If multiple edges are allowed between vertices, the graph is known as a multigraph. Vertices are usually not allowed to be self-connected, but this restriction is sometimes relaxed to allow such "graph loops." A graph that may contain multiple edges and graph loops is called a pseudograph.
The edges, vertices, or both of a graph may be assigned specific values, labels, or colors, in which case the graph is called a labeled graph. A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. Similarly, an edge coloring is an assignment of labels or colors to each edge of a graph such that adjacent edges (or the edges bounding different regions) must receive different colors. The assignment of labels or colors to the edges or vertices of a graph based on a set of specified criteria is known as graph coloring. If labels or colors are not permitted so that edges and vertices do not carry any additional properties beyond their intrinsic connectivities, a graph is called an unlabeled graph.
The edges of graphs may also be imbued with directedness. A normal graph in which edges are undirected is said to be undirected. Otherwise, if arrows may be placed on one or both endpoints of the edges of a graph to indicate directedness, the graph is said to be directed. A directed graph in which each edge is given a unique direction (i.e., edges may not be bidirected and point on both directions as once) is called an oriented graph. A graph or directed graph together with a function which assigns a positive real number to each edge (i.e., an oriented edge-labeled graph) is known as a network.
Rather amazingly, there are always an even number of odd vertices (i.e., vertices having an odd number of edges incident on them) for any simple graph.
A large number of operations can be defined on collections of graphs. For example, graph sums, differences, powers, unions, and products can be defined, as can graph eigenvalues.
Formally, graphs may be considered as the one-dimensional case of the more general complexes.
OTHER NOTES:
Informally, a graph is a diagram consisting of points, called vertices, joined together by lines, called edges; each edge joins exactly two vertices. A graph G is a triple consisting of a vertex set of V(G), an edge set E(G), and a relation that associates with each edge two vertices (not necessarily distinct) called its endpoints.
Definition of Graph
A graph G = (V, E) consists of V, a non empty set of vertices or nodes and E, a set of edges. Each edge has either one or two verticies associated with it, called its endpoints. An edge is said to connect its endpoints.
Formally, a graph G is an ordered pair of dsjoint sets (V, E), where E Í V × V. Set V is called the vertex or node set, while set E is the edge set of graph G. Typically, it is assumed that self-loops (i.e. edges of the form (u, u), for some u Î V) are not contained in a graph.
Directed and Undirected Graph
A graph G = (V, E) is directed if the edge set is composed of ordered vertex (node) pairs. A graph is undirected if the edge set is composed of unordered vertex pair.
Vertex Cardinality
The number of vertices, the cardinality of V, is called the order of graph and denoted by |V|. We usually use n to denote the order of G. The number of edges, the cardinality of E, is called the size of graph and denoted by |E|. We usually use m to denote the size of G.
Neighbor Vertex and Neighborhood
We write vivj Î E(G) to mean {vi, vj}Î E(G), and if e = vi vj Î E(G), we say vi and vj are adjacent.
Formally, given a graph G = (V, E), two vertices vi , vj Î V are said to be neighbors, or adjacent nodes, if ( vi , vj ) Î E. If G is directed, we distinguish between incoming neighbors of vi (those vertices vj Î V such that (vj, vi) Î E) and outgoing neighbors of vi (those vertices vj ÎV such that (vi, vj) Î E).
The open neighborhood N(v) of the vertex v consists of the set vertices adjacent to v, that is, N(v) = {w Î v : vw Î E}. The closed neighborhood of v is N[v] = N(v) È {v}. For a set S Í V, the open neighborhood N(S) is defined to be UvÎSN(v), and the closed neighborhood of S is N[S] = N(S) È S.
Vertex Degree
The degree deg(v) of vertex v is the number of edges incident on v or equivalently, deg(v) = |N(v)|. The degree sequence of graph is (deg(v1), deg(v2), ..., deg(vn)), typically written in nondecreasing or nonincreasing order. The minimum and maximum degree of vertices in V(G) are denoted by d(G) and ∆(G), respectively. If d(G) = ∆(G) = r, then graph G is said to be regular of degree r, or simply r-regular.
Formally, given a graph G = (V, E), the degree of a vertex v Î V is the number of its neighbors in the graph. That is,
deg(v) = | {u Î V : (v, w) Î E}|.
If G is directed, we distinguish between in-degree (nimber of incoming neighbors) and out-degree (number of outgoing neighbors) of a vertex.
Loop and Multiple Edges
A loop is an edge whose endpoints are equal i.e., an edge joining a vertex to it self is called a loop. We say that the graph has multiple edges if in the graph two or more edges joining the same pair of vertices.
Simple Graph
A graph with no loops or multiple edges is called a simple graph. We specify a simple graph by its set of vertices and set of edges, treating the edge set as a set of unordered pairs of vertices and write e = uv (or e = vu) for an edge e with endpoints u and v.
When u and v are endpoints of an edge, they are adjacent and are neighbors.
Connected Graph
A graph that is in one piece is said to be connected, whereas one which splits into several pieces is disconnected.
A graph G is connected if there is a path in G between any given pair of vertices, otherwise it is disconnected. Every disconnected graph can be split up into a number of connected subgraphs, called components.
Subgraph
Let G be a graph with vertex set V(G) and edge-list E(G). A subgraph of G is a graph all of whose vertices belong to V(G) and all of whose edges belong to E(G). For example, if G is the connected graph below:
where V(G) = {u, v, w, z} and E(G) = (uv, uw, vv, vw, wz, wz} then the following four graphs are subgraphs of G.
Degree (or Valency)
Let G be a graph with loops, and let v be a vertex of G. The degree of v is the number of edges meeting at v, and is denoted by deg(v).
For example, consider, the following graph G
The graph G has deg(u) = 2, deg(v) = 3, deg(w) = 4 and deg(z) = 1.
Regular Graph
A graph is regular if all the vertices of G have the same degree. In particular, if the degree of each vertex is r, the G is regular of degree r.
The Handshaking Lemma In any graph, the sum of all the vertex-degree is equal to twice the number of edges.
Proof Since each edge has two ends, it must contribute exactly 2 to the sum of the degrees. The result follows immediately.
The Following are the consequences of the Handshaking lemma.
- In any graph, the sum of all the vertex-degree is an even number.
- In any graph, the number of vertices of odd degree is even.
- If G is a graph which has n vertices and is regular of degree r, then G has exactly 1/2 nr edges.
Isomorphic Graphs
Two graph G and H are isomorphic if H can be obtained from G by relabeling the vertices - that is, if there is a one-to-one correspondence between the vertices of G and those of H, such that the number of edges joining any pair of vertices in G is equal to the number of edges joining the corresponding pair of vertices in H. For example, two unlabeled graphs, such as
are isomorphic if labels can be attached to their vertices so that they become the same graph.
The word isomorphic derives from the Greek for same and form.
Walk
A walk of length k in a graph G is a succession of k edges of G of the form uv, vw, wx, . . . , yz.
We denote this walk by uvwx . . yz and refer to it as a walk between u and z.
Trail and Path
If all the edges (but no necessarily all the vertices) of a walk are different, then the walk is called a trail. If, in addition, all the vertices are difficult, then the trail is called path.
- The walk vzzywxy is a trail since the vertices y and z both occur twice.
- The walk vwxyz is a path since the walk has no repeated vertices.
Complete Graphs
A computer graph is a graph in which every two distinct vertices are joined by exactly one edge. The complete graph with n vertices is denoted by Kn.
The following are the examples of complete graphs.
The graph Kn is regular of degree n-1, and therefore has 1/2n(n-1) edges, by consequence 3 of the handshaking lemma.
Null Graphs
A null graphs is a graph containing no edges. The null graph with n vertices is denoted by Nn.
The following are the examples of null graphs.
Note that Nn is regular of degree 0.
Cycle Graphs
A cycle graph is a graph consisting of a single cycle. The cycle graph with n vertices is denoted by Cn.
The following are the examples of cyclic graphs.
Note that Cn is regular of degree 2, and has n edges.
Path Graphs
A path graph is a graph consisting of a single path. The path graph with n vertices is denoted by Pn.
The following are the examples of path graphs.
Note that path graph, Pn, has n-1 edges, and can be obtained from cycle graph, Cn, by removing any edge.
Bipartite Graphs
A bipartite graph is a graph whose vertex-set can be split into two sets in such a way that each edge of the graph joins a vertex in first set to a vertex in second set.
The examples of bipartite graphs are:
Complete Bipartite Graph
A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to each vertex in the second set by exactly one edge. The complete bipartite graph with r vertices and 3 vertices is denoted by Kr,s.
The following are some examples.
Note that Kr,s has r+s vertices (r vertices of degrees, and s vertices of degree r), and rs edges. Note also that Kr,s = Ks,r.
An Important Note: A complete bipartite graph of the form Kr,s is called a star graph.
