ABSTRACT
This study delves into the intricate world of directed graphs, or digraphs, to explore and analyze various fundamental properties. By examining concepts such as connectivity and cycles, this research aims to shed light on the underlying structures and behaviors of digraphs. Through rigorous mathematical analysis and computational techniques, this investigation seeks to enhance our understanding of these essential mathematical structures, paving the way for their applications in various domains such as network theory, computer science, and social sciences.
TABLE OF CONTENTS
DECLARATION ii
CERTIFICATION iii
DEDICATION iv
ACKNOWLEDGEMENTS v
ABSTRACT vi
TABLE OF CONTENTS vii
CHAPTER
INTRODUCTION
1.1 History of Digraph (directed graph) theory 9
1.2 Origin and the Notion of Digraphs 10
1.3 Motivation and Background 10
1.4 Aims and Objectives 10
1.5 Definition of terms 11
1.5.1 Directed graph: 11
1.5.2 Order of D 11
1.5.3 Size of D 11
1.5.4 Isomorphism 11
1.5.5 Subdigraph 12
1.5.6 Symmetry 12
1.5.7 Regular Digraph 12
1.6.8 Weakly Connected 12
1.5.9 Strongly Connected 13
1.5.10 Eccentricity 13
1.5.11 Eulerian Circuit and Trail 13
1.5.12 Hamiltonian Graph 14
1.5.13 Tournament 14
1.5.14 Acyclic 15
1.5.15 King in Tournament 15
CHAPTER TWO
LITERATURE REVIEW
2.1 Introduction 16
2.2 Subdigraph 18
Types of Digraphs 19
2.3 Connected Diagraphs: 19
2.4 Distance in a Digraph 20
2.5 Eulerian Diagraphs 22
2.6 Hamiltonian Digraph 23
Theorem 2.6.1 (Meyniel’s theorem) 23
CHAPTER THREE
TOURNAMENTS
3.1 Introduction of Tournament 24
3.2 Tournament 24
3.3 Types of Tournament 25
3.3.1 Triple and bipatile tournament 25
3.4 Transitive Tournaments. 27
CHAPTER FOUR
APPLICATIONS OF DIGRAPH
4.1 Introduction 33
4.2 Game Theory 33
4.3 Signal-Flow Graphs 35
CHAPTER FIVE
SUMMARY, RECOMMENDATION AND CONCLUSION
Summary 38
Recommendation 38
5.3 conclusion 38
REFERENCES 40
CHAPTER ONE
INTRODUCTION
1.1 History of Digraph (directed graph) theory
The history of Digraph theory or study of directed graph can be traced back to the late 19th and early 20th centuries when mathematicians began to explore the properties of directed graph systematically. Here are some key milestones in the history of digraph theory.
Early Development: The concept of directed graph can be traced back to the 18th century but formal investigations began in the late 19th century. Sir Arthur Cayley a British mathematician made contributions to this field in the 19th century.
Eulerian paths and Hamiltonian Cycles: In the 18th century Leonhard Euler introduced the concept of Eulerian paths and circuits in undirected graphs. The study of these concept later extended to directed graphs, leading to the exploration of directed Eulerian path and Hamiltonian cycles.
Network flow: During the world war II with the work of George dantzig and others.
Planar digraph in the 1960s, by William Tutte made substantial progress in understanding planar digraph, which are directed graphs that can embedded a plane without edge crossings.
Modern Application: Today digraph theory finds application in various fields, including computer, network, social networks, transportation system and biological network.
Overall, digraph theory has evolved significantly over the year with contribution from various mathematician and researchers, making it a fundamental area of graph theory with diverse application indifferent domain.
1.2 Origin and the Notion of Digraphs
The basic idea of digraph theory was introduced by the famous mathematician Leonard Euler in 1735, a Swiss mathematician while he was solving the new seven bridges of Konisberg in 1736. Euler famous paper on the “Seven Bridges of Konisberg” is often considered the starting point of the digraph theory. Euler tackles a problem concerning the city of Konisberg (now Kallningrad) and whether it was possible to cross each of the seven bridges at once and return to the starting point. To solve this problem, Euler abstracted the land masses and bridge as nodes and edges, creating the first-ever graph.
1.3 Motivation and Background
In the past 50 years, digraph theory has had many practical applications in various field discipliners, including Operation research, Biological Science, chemistry, Computer Science Economics, Engineering information and linguistics, Mathematics, Medicine, Social Science etc.
Digraphs are excellent modeling tool and mathematical abstraction that is useful for solving many kinds of problems. A digraph
1.4 Aim and Objectives
The objectives of this project are as follows:
i. To develop and understanding in basic concept of digraph.
ii. To develop and understanding of the properties of diagraph.
iii. To discuss the types of digraph and use the formula, theorem and corollary to understand
iv. To provide the several example in the application of digraph theory
1.5 Definition of terms
1.5.1 Directed graph:
A digraph is a finite non empty set of object called vertices, together with a (possibly empty) set of order pair of distinct vertices of D called arcs or directed edge
1.5.2 Order of D
The cardinality of a vertex of the digraph D is called the order of D, and is ordinarily denoted by n.
1.5.3 Size of D
The cardinality of its arc set of the digraph is called the size of D, and it is ordinarily denoted by m.
1.5.4 Isomorphism
A digraph D1 is isomorphic to a diagraph D2 written as D1≅D2 if there exist a bijective function φV(D1)→V(D2) such that (u,v)∈E(D1) if and only if (φ(u),φ(v))∈E(D2) then the function φ is called an isomorphism from D1 to D2.
1.5.5 Subdigraph
A digraph D1 is a subdigraph of a digraph D if V(D1)⊆V(D) and E(D1)⊆E(D). D1is a spanning subdigraph od D if V(D1)=V(D)
1.5.6 Symmetry
A digraph is symmetry if (u,v) is an arc of D and (v,u)is also an arc of D
1.5.7 Regular Digraph
A digraph D is regular of degree r or r-regular if odv=idv=r for every vertex u of D
1.5.8 Weakly Connected
A digraph is weakly connected if the underlying graph of D is connected
1.5.9 Strongly Connected
A digraph D is strongly connected if for every pair u,v of vertices D contains both a u→v path and v→u path.
1.5.10 Eccentricity
Eccentricity can be defined as before as well as radius and diameter in a strong digraph.
1.5.11 Eulerian Circuit and Trail
An Eulerian Circuit in a connected diagraph D is a circuit that contain every arc of D. while Eulerian trail in D is an open trail that contain every arc of D. Aconnected digraph that contain an Eulerian circuit is called an Eulerian digraph.
1.5.12 Hamiltonian Graph
A digraph D is Hamiltonian if D contains a spanning cycle, such a cycle is called a Hamiltonian cycle. As with Hamiltonian graph no characterization of Hamiltonian digraphs exist.
1.5.13 Tournament
A tournament is an orientation of a complete graph. A tournament can be defined as a digraph such that for every pair u,v of distinct vertices exactly one of (u,v) and (v,u) is an arc and it is denoted by T.
A tournament T is transitive if whenever (u,v) and (v,w) are arc of T, the (u,w) is also arc of T.
1.5.14 Acyclic
An acyclic digraph is a digraph having no cycles
1.5.15 King in Tournament
Definition: A vertex u in a tournament T is a king if for every vertex w different from u either u→w or there exist a vertex v such that u→v→w. The large number of arc in a tournament often produce path and cycles of varying length. A path in a diagraph D containing every vertex of D is a Hamiltonian path.
Click “DOWNLOAD NOW” below to get the complete Projects
FOR QUICK HELP CHAT WITH US NOW!
+(234) 0814 780 1594
Buyers has the right to create
dispute within seven (7) days of purchase for 100% refund request when
you experience issue with the file received.
Dispute can only be created when
you receive a corrupt file, a wrong file or irregularities in the table of
contents and content of the file you received.
ProjectShelve.com shall either
provide the appropriate file within 48hrs or
send refund excluding your bank transaction charges. Term and
Conditions are applied.
Buyers are expected to confirm
that the material you are paying for is available on our website
ProjectShelve.com and you have selected the right material, you have also gone
through the preliminary pages and it interests you before payment. DO NOT MAKE
BANK PAYMENT IF YOUR TOPIC IS NOT ON THE WEBSITE.
In case of payment for a
material not available on ProjectShelve.com, the management of
ProjectShelve.com has the right to keep your money until you send a topic that
is available on our website within 48 hours.
You cannot change topic after
receiving material of the topic you ordered and paid for.
Login To Comment