Graphs Paths

Graphs Paths

The notion of a path in a graph is intuitively clear but a little hard to pin down formally.
Suppose G(V,E) is a graph with vertices v0,v1,…,vk (not necessarily distinct) and edges e1,e2,…,ek (not necessarily distinct) in which edge ei={vi-1,vi} for i=1,…,k. Then the alternating sequence of vertices and edges v0e1v1e2v2…ekvk is a path from v0 to vk of length k (note that the length is the number of edges, not vertices). Unless we work with multigraphs the listing of the edges is redundant, so we may speak more simply of the path as v0v1v2…vk. This definition allows for incredibly knotty, repetitious paths. If we want to rule out that possibility, we can speak of simple paths, which are paths in which no vertices (and thus no edges) are repeated.

Polyhedral Graph

Polyhedral Graph is A graph made up of the vertices and edges of a polyhedron. Polyhedral graphs are always planar.


In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of aconvex polyhedron. According to Steinitz's theorem, the polyhedral graphs may also be characterized in purely graph-theoretic terms, as the 3-vertex-connected planar graphs.

Planar Graph

Planar Graph

A graph that can be drawn in a plane without any graph edges intersecting.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other.

A planar graph already drawn in the plane without edge intersections is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point in 2D space, and from every edge to a plane curve, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. Plane graphs can be encoded by combinatorial maps.

It is easily seen that a graph that can be drawn on the plane can be drawn on the sphere as well, and vice versa.

The equivalence class of topologically equivalent drawings on the sphere is called a planar map. Although a plane graph has an external orunbounded face, none of the faces of a planar map have a particular status.

Graph cycle

Graph cycle

Any of a graph's edge-set subsets that forms a path, the first node of which is also the last.

Graph theory

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.