Question

I need definitions, descriptions, how to solve and example of the following:

•The Mathematics of Graphs

•Graphs and Euler circuits

•Weighted graphs

•Euler’s formula

•Graph Coloring

Answer 1

Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines).

An Euler circuit is a circuit that uses every edge of a graph exactly once.An Euler circuit starts and ends at the same vertex. Suppose that a graph G has an Euler circuit C. For every vertex v in G, each edge having v as an endpoint shows up exactly once in C. The circuit C enters v the same number of times that it leaves v (say s times), so v has degree 2s. That is, v must be an even vertex.

Removing a single edge from a connected graph can make it
disconnected. Such an edge is called a bridge.

To find an Euler circuit:
1. Make sure the graph has either 0 or 2 odd vertices.
2. If there are 0 odd vertices, start anywhere. If there are 2
odd vertices, start at one of them.
3. Follow edges one at a time. If you have a choice between
a bridge and a non-bridge, always choose the non-bridge.
4. Stop when you run out of edges.
This is called Fleury’s algorithm, and it always works!

Example Here’s a couple, starting and ending at vertex A: ADEACEFCBA and AECABCFEDA. The second is shown in arrows.

weighted graph

A weighted graph is a graph in which each branch is given a numerical weight. A weighted graph is therefore a special type of labeled graph in which the labels are numbers (which are usually taken to be positive).

Example

Euler's formula Let G be a connected and not necessarily simple plane graph with v vertices, e edges, and f faces. Then v+ f = e + 2.The Euler formula tells us that all plane drawings of a connected planar graph have the same number of faces namely, 2+e-v.

Example

Graph Coloring

graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Vertex coloring is the starting point of graph coloring.​

Chromatic Number: The smallest number of colors needed to color a graph G is called its chromatic number and it is denoted by X(G).

Example

Take a look at the following graph. The regions ‘aeb’ and ‘befc’ are adjacent, as there is a common edge ‘be’ between those two regions.

Similarly the other regions are also coloured based on the adjacency. This graph is coloured as follows −

Answer 2