Graph theory
Graph theory, the study of graphs and networks, is often considered part of combinatorics, but has grown large enough and distinct enough, with its own kind of problems, to be regarded as a subject in its own right.Graphs are one of the prime objects of study in Discrete Mathematics. They are among the most ubiquitous models of both natural and human-made structures. They can model many types of relations and process dynamics in physical, biological and social systems. In computer science, they represent networks of communication, data organization, computational devices, the flow of computation, etc. In Mathematics, they are useful in Geometry and certain parts of Topology, e.g. Knot Theory.Algebraic graph theory has close links with group theory. There are also continuous graphs, however for the most part research in graph theory falls within the domain of discrete mathematics
.
Ref :Wikipedia
or
A graph, G, comprises a set V of vertices and a set E of edges. The vertex set can be anything, but is most commonly a collection of letters or numbers. The set of edges is a set of doubleton subsets of V. That is E⊆{{a,b}:a,b∈V and a≠b}. We denote the graph by G(V,E). If G(V,E) is a graph and {a,b}∈E, then we say vertices a and b are adjacent and the edge {a,b} joins them or connects them or is incident on them. We call a and b the endpoints of the edge. Two edges that share one vertex, such as {a,b} and {b,c} with a≠c, are adjacent to each other.
Our definition of graph does not allow an edge to join a vertex to itself. Such an edge is called a loop, and some definitions of graph allow them. Our text refers to such a structure as a graph with loops (clever, huh?), which is a straightforward name but not common as far as I know. Some definitions of graph allow for multiple edges between the same two vertices. Our book calls this structure a multigraph (which is a common and helpful usage in that it makes E a multiset rather than a set). Our book calls a multigraph with loops a pseudograph. I think this terminology may be standard, but I am not a graph theorist.
The degree of a vertex is the number of edges incident on the vertex. That is, if G(V,E) is a graph and a∈V, then degree(a)=|{x:{a,x}∈E}|. Put another way, the degree of a vertex is the number of vertices adjacent to it. If a vertex has no adjacent vertices (degree 0), then it is isolated.
.
Ref :Wikipedia
or
A graph, G, comprises a set V of vertices and a set E of edges. The vertex set can be anything, but is most commonly a collection of letters or numbers. The set of edges is a set of doubleton subsets of V. That is E⊆{{a,b}:a,b∈V and a≠b}. We denote the graph by G(V,E). If G(V,E) is a graph and {a,b}∈E, then we say vertices a and b are adjacent and the edge {a,b} joins them or connects them or is incident on them. We call a and b the endpoints of the edge. Two edges that share one vertex, such as {a,b} and {b,c} with a≠c, are adjacent to each other.
Our definition of graph does not allow an edge to join a vertex to itself. Such an edge is called a loop, and some definitions of graph allow them. Our text refers to such a structure as a graph with loops (clever, huh?), which is a straightforward name but not common as far as I know. Some definitions of graph allow for multiple edges between the same two vertices. Our book calls this structure a multigraph (which is a common and helpful usage in that it makes E a multiset rather than a set). Our book calls a multigraph with loops a pseudograph. I think this terminology may be standard, but I am not a graph theorist.
The degree of a vertex is the number of edges incident on the vertex. That is, if G(V,E) is a graph and a∈V, then degree(a)=|{x:{a,x}∈E}|. Put another way, the degree of a vertex is the number of vertices adjacent to it. If a vertex has no adjacent vertices (degree 0), then it is isolated.
No comments:
Post a Comment