# Graph Theory

### Spanning Tree

3 min read

Introduction: A spanning tree is a spanning subgraph, that is a tree. In Other words a

*spanning tree*for a connected graph`G`is a subgraph of`G`that is a tree and whose vertex set is all the vertices of`G.`If`G`is a tree then it has only one spanning tree,`G`itself. If`G`is not a tree it has more than one spanning tree. Consider the following problem. In the diagram shown below we have four wells in an offshore oilfield (nodes 1 to 4 below) and an on-shore terminal (node 5 below). The four wells in this field must be connected together via a pipeline network to the on-shore terminal. The various pipelines that can be constructed are shown as links in the diagram below and the cost of each pipeline is given next to each link. What pipelines would you recommend be built?Basic Electrical Engineering

Automobile Engineering

Maths for Engineers - 1

Human Values & Prof. Ethics-1

Operations Research

Quality Control Engineering

Six Sigma

Total Quality Management (TQM)

Maths for Engineers - 2

Physics for Engineers - 2

Maths for Engineers - 3

Graph Theory

Physics for Engineers - 1

Control Systems - 1

Neural Network & Fuzzy Systems

Real Time Systems

Automata | Comp. Sc. Engg.

Data Mining & Data Warehousing

Numerical Methods

Mechatronics

Artificial Intelligence

Design Analysis of Algorithm

Discrete Mathematics

Automobile Engineering

Maths for Engineers - 1

Human Values & Prof. Ethics-1

Operations Research

Quality Control Engineering

Six Sigma

Total Quality Management (TQM)

Maths for Engineers - 2

Physics for Engineers - 2

Maths for Engineers - 3

Graph Theory

Physics for Engineers - 1

Control Systems - 1

Neural Network & Fuzzy Systems

Real Time Systems

Automata | Comp. Sc. Engg.

Data Mining & Data Warehousing

Numerical Methods

Mechatronics

Artificial Intelligence

Design Analysis of Algorithm

Discrete Mathematics