FACTOID # 8: Bookworms: Vermont has the highest number of high school teachers per capita and third highest number of librarians per capita.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Graph (mathematics)
A drawing of a labeled graph on 6 vertices and 7 edges.
A drawing of a labeled graph on 6 vertices and 7 edges.

In mathematics and computer science, a graph is the basic object of study in graph theory. Informally speaking, a graph is a set of objects called points, nodes, or vertices connected by links called lines or edges. In a proper graph, which is by default undirected, a line from point A to point B is considered to be the same thing as a line from point B to point A. In a digraph, short for directed graph, the two directions are counted as being distinct arcs or directed edges. Typically, a graph is depicted in diagrammatic form as a set of dots (for the points, vertices, or nodes), joined by curves (for the lines or edges). A drawing of a graph. ... relation graph theory In mathematics, the graph of a function f is the collection of all ordered pairs (x,f(x)). In particular, graph means the graphical representation of this collection, in the form of a curve or surface, together with axes, etc. ... Image File history File links 6n-graf. ... Image File history File links 6n-graf. ... As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A drawing of a graph. ...

Contents

Definitions

Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures.


Graph

A graph or undirected graph G is an ordered pair G: = (V,E) that is subject to the following conditions: Image File history File links Undirected. ... In mathematics, an ordered pair is a collection of two not necessarily distinct objects, one of which is distinguished as the first coordinate (or first entry or left projection) and the other as the second coordinate (second entry, right projection). ...

  • V is a set, whose elements are called vertices or nodes,
  • E is a set of pairs (unordered) of distinct vertices, called edges or lines.

The vertices belonging to an edge are called the ends, endpoints, or end vertices of the edge. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...


V (and hence E) are usually taken to be finite sets, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case. The order of a graph is | V | (the number of vertices). A graph's size is | E | , the number of edges. The degree of a vertex is the number of other vertices it is connected to by edges.


The edge set E induces a symmetric binary relation ~ on V that is called the adjacency relation of G. Specifically, for each edge {u,v} the vertices u and v are said to be adjacent to one another, which is denoted u ~ v.


For an edge {u, v}, graph theorists usually use the somewhat shorter notation uv.


Various Types Of Graphs

Directed graph

A directed graph or digraph G is an ordered pair G: = (V,A) with Image File history File links Directed. ...

  • V is a set, whose elements are called vertices or nodes,
  • A is a set of ordered pairs of vertices, called directed edges, arcs, or arrows.

An arc e = (x,y) is considered to be directed from x to y; y is called the head and x is called the tail of the arc; y is said to be a direct successor of x, and x is said to be a direct predecessor of y. If a path leads from x to y, then y is said to be a successor of x, and x is said to be a predecessor of y. The arc (y,x) is called the arc (x,y) inverted. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. ...


A directed graph is called symmetric if every arc belongs to it together with the corresponding inverted arc. A symmetric loopless directed graph is equivalent to an undirected graph with the pairs of inverted arcs replaced with edges; thus the number of edges is equal to the number of arcs halved.


A variation on this definition is the oriented graph, which is a graph (or multigraph; see below) with an orientation or direction assigned to each of its edges. A distinction between a directed graph and an oriented simple graph is that if x and y are vertices, a directed graph allows both (x,y) and (y,x) as edges, while only one is permitted in an oriented graph. A more fundamental difference is that, in a directed graph (or multigraph), the directions are fixed, but in an oriented graph (or multigraph), only the underlying graph is fixed, while the orientation may vary.


A directed acyclic graph, occasionally called a dag or DAG, is a directed graph with no directed cycles. A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path that starts and ends on v. ... In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ...


A quiver is simply a directed graph, but the context is different. When discussing quivers emphasis is placed on representations of the graph where vector spaces are attached to the vertices and linear transformations are attached to the arcs. In mathematics, a quiver is a directed graph where loops and multiple arrows between two vertices are allowed. ... In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ... In mathematics, a linear transformation (also called linear map or linear operator) is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. ...


Undirected graph

A graph G={V,E} in which every edge is undirected.


Finite Graph

if G=<V,E> be a graph, such that V(G) and E(G) are finite sets, then G is called finite graph


Simple Graph

An undirected graph which has no self-loops is called a simple graph.


Linear Graph

A graph is a linear graph if its each edge joining vertices lies along a line.


Regular Graph

A regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k.


Weighted Graph

A graph is called weighted graph if positive number of weight is assigned to each edge. Those number repersent costs, length or capacities etc depending on the problem.


Weight of the graph is sum of the weight given to all edges.


Mixed graph

A mixed graph G is a graph in which some edges may be directed and some may be undirected. It is written as an ordered triple G := (V, E, A) with V, E, and A defined as above. Directed and undirected graphs are special cases.


Complete graph

Complete graphs have the feature that each pair of vertices has an edge connecting them.


Variations in the definitions

As defined above, edges of undirected graphs have two distinct ends, and E and A are sets (with distinct elements, like all sets). Many applications require more general possibilities, but terminology varies. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...


Loop

A loop is an edge (directed or undirected) which starts and ends on the same vertex; these may be permitted or not permitted according to the application. In this context, an edge with two different ends is called a link. A graph with 6 vertices (nodes) and 7 edges. ...


Multiset

Sometimes E and A are allowed to be multisets, so that there can be more than one edge (called multiple edges) between the same two vertices. Another way to allow multiple edges is to make E a set, independent of V, and to specify the endpoints of an edge by an incidence relation between V and E. The same applies to a directed edge set A, except that there must be two incidence relations, one for the head and one for the tail of each edge. In mathematics, a multiset (or bag) is a generalization of a set. ... Multiple edges joining two vertices. ... In mathematics, the incidence matrix of an undirected graph G is a p × q matrix where p and q are the number of vertices and edges respectively, such that if the vertex and edge are incident and 0 otherwise. ...


Multi Graph

The term "multigraph" is generally understood to mean that multiple edges (and sometimes loops) are allowed. Where graphs are defined so as to allow loops and multiple edges, a multigraph is often defined to mean a graph without loops,[1] however, where graphs are defined so as to disallow loops and multiple edges, the term is often defined to mean a "graph" which can have both multiple edges and loops,[2] although many use the term "pseudograph" for this meaning.[3] A multigraph is a graph with multiple edges, i. ... This article just presents the basic definitions. ...


Halfedge

In exceptional situations it is even necessary to have edges with only one end, called halfedges, or no ends (loose edges); see for example signed graphs. In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. ...


Properties of graphs

For more definitions see Glossary of graph theory.

Two edges of a graph are called adjacent (sometimes coincident) if they share a common vertex. Two arrows of a directed graph are called consecutive if the head of the first one is at the nock (notch end) of the second one. Similarly, two vertices are called adjacent if they share a common edge (consecutive if they are at the notch and at the head of an arrow), in which case the common edge is said to join the two vertices. An edge and a vertex on that edge are called incident. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... Nock may refer to: Nock - the notch in the end of an arrow Nock - to mount an arrow unto a bow (when used as a verb) Nock - members of the Nock family of gunsmiths in England Henry Nock (1741–1805) - gunsmith who also founded Wilkinson Sword in 1772 Samuel Nock...


The graph with only one vertex and no edges is called the trivial graph. A graph with only vertices and no edges is known as an edgeless graph. The graph with no vertices and no edges is sometimes called the null graph or empty graph, but not all mathematicians allow this object.


In a weighted graph or digraph, each edge is associated with some value, variously called its cost, weight, length or other term depending on the application; such graphs arise in many contexts, for example in optimal routing problems such as the traveling salesman problem. The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...


Normally, the vertices of a graph, by their nature as elements of a set, are distinguishable. This kind of graph may be called vertex-labeled. However, for many questions it is better to treat vertices as indistinguishable; then the graph may be called unlabeled. (Of course, the vertices may be still distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges). The same remarks apply to edges, so that graphs which have labeled edges are called edge-labeled graphs. Graphs with labels attached to edges or vertices are more generally designated as labeled. Consequently, graphs in which vertices are indistinguishable and edges are indistinguishable are called unlabeled. (Note that in the literature the term labeled may apply to other kinds of labeling, besides that which serves only to distinguish different vertices or edges.)


Examples

The picture is a graphic representation of the following graph Image File history File links 6n-graf. ...

  • V: = {1,2,3,4,5,6}
  • E: = {{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

The fact that vertex 1 is adjacent to vertex 2 is sometimes denoted by 1 ~ 2.

In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, categories allow one to formalize notions involving abstract structure and processes that preserve structure. ... A multigraph is a graph with multiple edges, i. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ... In category theory, a branch of mathematics, a functor is a special type of mapping between categories. ... In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Fig. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...

Important graphs

Basic examples are:

  • In a complete graph each pair of vertices is joined by an edge, that is, the graph contains all possible edges.
  • In a complete bipartite graph, the vertex set is the union of two disjoint subsets, W and X, so that every vertex in W is adjacent to every vertex in X but there are no edges within W or X.
  • In a bipartite graph, the vertices can be divided into two sets, W and X, so that every edge has one vertex in each of the two sets.
  • In a path of length n, the vertices can be listed in order, v0, v1, ..., vn, so that the edges are vi−1vi for each i = 1, 2, ..., n.
  • A cycle or circuit of length n is a closed path without self-intersections; equivalently, it is a connected graph with degree 2 at every vertex. Its vertices can be named v1, ..., vn so that the edges are vi−1vi for each i = 2,...,n and vnv1
  • A planar graph can be drawn in a plane with no crossing edges (i.e., 'embedded in a plane).
  • A forest is a graph with no cycles.
  • A tree is a connected graph with no cycles.

More advanced kinds of graphs are: In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. ... In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ... In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets and such that no edge has both end-points in the same set. ... In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. ... This article is about connected, 2-regular graphs. ... In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. ... In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

The Petersen graph has crossing number 2. ... In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. ... In graph theory, a cograph, or P4-free graph, is a graph that fulfills the following equivalent properties: Can be constructed from isolated vertices by complement, joint union and disjoint union. ... In mathematics, an automorphism is an isomorphism from a mathematical object to itself. ... In mathematics, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism f : G &#8594; G such that f ( v1 ) = v2. ... In mathematics, an arc-transitive graph is a graph G such that, given any two edges e1 = u1v1 and e2 = u2v2 of G, there are two automorphisms f : G → G, g : G → G such that f (e1) = e2, g (e1) = e2 and f (u1) = u2, f (v1) = v2, g (u1... In mathematics, a distance-transitive graph is a graph (mathematics) such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors. ... In mathematics, a distance-regular graph is a regular graph (mathematics) such that, given any two vertices v and w at any distance i, the number of vertices adjacent to w and at distance j from v depends only on i and j, not on the particular pair of vertices. ...

Operations on graphs

Main article: Operations on graphs

There are several operations that produce new graphs from old ones. They may be separated into three categories Operations on graphs produce new graphs from old ones. ...

In graph theory, the line graph L(G) of a graph G is a graph such that each node of L(G) represents an edge of G; and any two nodes of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common... G′is the dual graph of G Dual graph is a term used in the mathematical study of graphs. ... In graph theory the complement or inverse of a graph is a graph on the same vertices such that two vertices of are adjacent if and only if they are not adjacent in . ... Operations on graphs produce new graphs from old ones. ... In graph theory, the cartesian product G H of graphs G and H is a graph such that the vertex set of G H is the cartesian product V(G) V(H); and any two vertices (u,u) and (v,v) are adjacent in G H if and only if... In graph theory, the tensor product or categorical product G H of graphs G and H is a graph such that the vertex set of G H is the cartesian product V(G) V(H); and any two vertices (u,u) and (v,v) are adjacent in G H if... A graph product is a binary operation on graphs. ... The lexicographic product of graphs. ...

Generalizations

In a hypergraph, an edge can join more than two vertices. Sample of hypergraph: , . In mathematics, a hypergraph is a generalization of a graph, where edges can connect any number of vertices. ...


An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices. In mathematics, a simplicial complex is a topological space of a particular kind, built up of points, line segments, triangles, and their n-dimensional counterparts. ... A 3-simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) or n-simplex is an n-dimensional analogue of a triangle. ...


Every graph gives rise to a matroid. In combinatorial mathematics, a matroid is a structure that captures the essence of a notion of independence (hence independence structure) that generalizes linear independence in vector spaces. ...


In model theory, a graph is just a structure. But in that case, there is no limitation on the number of edges: it can be any cardinal number. In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined... Aleph-0, the smallest infinite cardinal In mathematics, cardinal numbers, or cardinals for short, are a generalized kind of number used to denote the size of a set, known as its cardinality. ...


Notes

  1. ^ For example, see Balakrishnan, p. 1, Gross (2003), p. 4, and Zwillinger, p. 220.
  2. ^ For example, see. Bollobas, p. 7 and Diestel, p. 25.
  3. ^ Gross (1998), p. 3, Gross (2003), p. 205, Harary, p.10, and Zwillinger, p. 220.

References

  • Balakrishnan, V. K., Graph Theory, McGraw-Hill; 1st edition (February 1, 1997). ISBN 0-07-005489-4.
  • Bollobas, Bela, Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
  • Diestel, Reinhard, Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
  • Gross, Jonathan L., and Yellen, Jay, Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
  • Gross, Jonathan L., and Yellen, Jay (eds.), Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2.
  • Harary, Frank, Graph Theory, Addison Wesley Publishing Company (January 1995). ISBN 0-201-41033-8.
  • Zwillinger, Daniel, CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.

See also

G′is the dual graph of G Dual graph is a term used in the mathematical study of graphs. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. ... As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... This is a list of important publications in mathematics, organized by field. ... This is a list of graph theory topics, by Wikipedia page. ... Network theory or diktyology is a branch of applied mathematics and physics, with the same general subject matter as graph theory. ... Look up polygon in Wiktionary, the free dictionary. ... In mathematics and physics, a quantum graph is a differential or pseudo-differential operator acting on functions defined on a metric graph. ... A tessellated plane seen in street pavement. ...

External links

  • Graph theory tutorial
  • Some graph theory algorithm animations
    • Step through the algorithm to understand it.
  • The compendium of algorithm visualisation sites
  • Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
  • Image gallery : Some real-life graphs
  • VisualComplexity.com - A visual exploration on mapping complex networks
  • Grafos Spanish copyleft software
  • Edge Addition Planarity Algorithm — Online version of a paper that describes the Boyer-Myrvold planarity algorithm.
  • Edge Addition Planarity Algorithm Source Code — Free C source code for reference implementation of Boyer-Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator.
  • Library of Efficient Models and Optimization in Networks — It is an open source C++ template library aimed at combinatorial optimization tasks, especially those working with graphs and networks.
  • Eric W. Weisstein, Graph at MathWorld.
  • TORSCHE Scheduling Toolbox for Matlab is a freely available toolbox of scheduling and graph algorithms.

  Results from FactBites:
 
AllRefer.com - graph (Mathematics) - Encyclopedia (215 words)
The graph of a function y=f (x) is the set of points with coordinates [x, f (x)] in the xy-plane, when x and y are numbers.
Statistics makes extensive use of both line graphs and bar graphs, in which the lengths of the various bars show the quantities to be compared.
Graph is also a mathematical term used in combinatorics to designate a geometric object consisting of vertices and edges (joining pairs of vertices).
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m