--%>
Assignment Help - homework help

  Theory of Graphs, Terminologies of graph and classification

Graphs:

The graph is a collection of vertices V and a collection of edges E comprising of pairs of vertices. Assume vertices as ‘locations’. The set of vertices is a set of all the possible positions. In this analogy, edges symbolize paths between pairs of such positions. The set E comprises all the paths among the positions.

Vertices and Edges:

The graph is generally symbolized using that analogy. Vertices are points or circles, edges are lines among them.

In this illustration graph:

248_g1.jpg

V = {1, 2, 3, 4, 5, 6}

E = {(1,3), (1,6), (2,5), (3,4), (3,6)}.

Each and every vertex is a member of the set V. The vertex is sometimes termed as node.

Each edge is a member of set E. Note that certain vertices might not be the end point of any edge. Such vertices are known as isolated.

At times, numerical values are related with edges, specifying lengths or costs; these graphs are termed as edge-weighted graphs (or weighted graphs). The value related with an edge is termed as the weight of edge. An identical definition holds for node-weighted graphs.

Terminology:

An edge is a self-loop when it is of the form (u,u). The sample graph comprises no self-loops.

A graph is simple when it neither comprises neither self-loops nor comprises an edge which is repeated in E. A graph is termed as multigraph if it comprises a given edge more than once or comprise self-loops. For discussions, graphs are supposed to be simple. The illustration graph is a simple graph.

An edge (u, v) is incident to both vertex u and vertex v. For example, the edge (1, 3) is incident to the vertex 3.

The degree of a vertex is the number of edges that are incident to it. For illustration, vertex 3 has degree 3, whereas vertex 4 has degree 1.

Vertex u is adjacent to vertex v when there is some edge, to which both are incident (i.e., there is an edge among them). For illustration, vertex 2 is adjacent to vertex 5.

A graph is state to be sparse when the total number of edges is small as compared to the total number possible ((N x (N-1))/2) and dense or else. For a given graph, whether it is dense or sparse is not well-defined.

Directed Graph:

Graphs explained therefore far are termed as undirected, as the edges go `both ways'. Up to now, the graphs have connoted that when one can travel from vertex 1 to vertex 3, one can as well travel from vertex 1 to vertex 3. In another words, (1, 3) being in the edge set entails (3, 1) is in the edge set.

773_g2.jpg

Sometimes, though, a graph is directed, in which case the edges encompass a direction. In this case, the edges are termed as arcs.

Directed graphs are drawn with the arrows to illustrate direction.

The out-degree of a vertex is the number of arcs that start at that vertex. The in-degree of a vertex is the number of arcs that end at that vertex. For illustration, vertex 6 has in-degree 2 and out-degree 1.

A graph is supposed to be undirected unless specifically termed as a directed graph.

Paths:

The path from vertex u to vertex x is a series of vertices (v 0, v 1, ..., v k) in such a way that v 0 = u and v k = x and (v 0, v 1) is an edge in the graph, as is (v 1, v 2), (v 2, v 3), and so on. The length of such a path is k.

2114_g3.jpg

For example, in the undirected graph above, (4, 3, 1, 6) is a path. This path is state to contain the vertices v 0, v 1, and so on and also the edges (v 0, v 1), (v 1, v 2) and so on.

Vertex x is state to be reachable from vertex u when a path exists from u to x.

The path is simple when it contains no vertex more than once.

A path is a cycle if it is a path from certain vertex to that similar vertex. A cycle is simple when it includes no vertex more than once, apart from the start (and end) vertex, that only appears as first and last vertex in the path.

Such definitions extend likewise to directed graphs (example: (v 0, v 1), (v 1, v 2), and so on should be arcs).

Graph Representation:

The choice of representation of a graph is important, as different representations contain very dissimilar time and space costs.

The vertices are usually tracked by numbering them, and hence one can index them just by their number.

Therefore, the representations concentrate on how to store the edges.

Edge List:

The most obvious manner to keep track of the edges is to maintain a list of pairs of vertices symbolizing the edges in the graph.

This symbolization is simple to code, pretty easy to debug, and pretty space efficient. Though, determining the edges incident to a given vertex is costly, as is determining if two vertices are adjacent. Adding an edge is fast, however deleting one is difficult if its position in the list is not recognized.

For weighted graphs, this symbolization as well keeps one more number for each edge, the edge weight. Extending this data structure to handle directed graphs is straight-forward. Symbolizing multi-graphs is as well trivial.

Illustration:

1938_g4.jpg

Connectedness:

1799_g5.jpg

The undirected graph is state to be connected when there is a path from each and every vertex to every other vertex. The illustration graph is not joined, as there is no path from vertex 2 to vertex 4. Though, if you add an edge between vertex 5 and vertex 6, then the graph becomes joined.

The component of a graph is a maximal subset of vertices in such a way that every vertex is reachable from all other vertex in the component. The initial illustration graph has two components: {1, 3, 4, 6} and {2, 5}. Note that {1, 3, 4} is not a component, as it is not the maximal.

The directed graph is state to be strongly connected when there is a path from each and every vertex to every other vertex.

The strongly connected component of a directed graph is a vertex u and the collection of all vertices v in such a way that there is a path from u to v and the path from v to u. 

Subgraphs:

Graph G' = (V', E') is a subgraph of G = (V, E) if V' is the subset of V and E' is a subset of E.

The subgraph of G induced by V' is a graph (V', E'), where E' comprises of all the edges of E which are between the members of V'. 

For illustration, for V' = {1, 3, 4, 2}, the subgraph is similar to the one shown:

676_g6.jpg

Complete Graph:

The graph is said to be complete when there is an edge between each and every pair of vertices.

1378_g7.jpg

Bipartite Graph:

The graph is said to be bipartite when the vertices can be divided into two sets V1 and V2 such that there are no edges between two vertices of V1 or two vertices of V2.

609_g8.jpg

Latest technology based Programming Languages Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.