Graph theory is the study of graphs, which are mathematical structures that are used to describe pairwise relationships between objects in mathematics. In this case, a graph is made up of vertices (also known as nodes or points) that are connected by edges (also called links or lines). Undirected graphs have edges that connect two vertices symmetrically, whereas directed graphs have edges that connect two vertices asymmetrically. Graphs are one of the most important subjects in discrete mathematics.
The Königsberg bridge issue was solved by Swiss mathematician Leonhard Euler in 1735, and this is when graph theory began. The Königsberg bridge issue was an ancient conundrum involving the possibility of finding a way over all seven bridges spanning a forked river running past an island without crossing any of them twice. There is no such path, according to Euler. He proved the first theorem in graph theory with only a few references to the actual layout of the bridges.
The term graph does not apply to data charts like line graphs or bar graphs, as it is used in graph theory. Instead, it refers to a collection of vertices (points or nodes) and edges (or lines) that link them. A multigraph is a graph in which two or more vertices are connected by more than one edge. A simple graph is one that is devoid of loops and has just one edge connecting any two vertices. Graph is presumed to relate to a basic graph unless otherwise specified. A full graph is defined as one in which each vertex is linked to every other vertex via an edge.
In this “Graph Theory - Mathematical Foundation of Computer Science” you will learn about the following topics:
- Definition of Graph Theory
- Directed and Undirected Graphs
- Walk, Path, Circuits
- Connected Components
- Connected Component Algorithm
- Shortest Path Algorithm
- Computer representation a graph
- Static Representation only, like Adjacency Matrix, Incidence Matrix, Path Matrix
- Bi-partite graphs, Regular graphs, Planar graphs, Euler graph
- Hamilton graph and their properties and characterization
- Application of graph theory in computer science (with example)
==== Point to Note ====
This article Graph Theory - Mathematical Foundation of Computer Science is contributed by Namrata Chaudhary, a student of Lumbini Engineering College (LEC).
If you like to contribute, you can mail us BCA Notes, BCA Question Collections, BCA Related Information, and Latest Technology Information at [email protected].
See your article appearing on BCA Notes (Pokhara University) main page with your designation and help other BCA Students to excel.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
 Notes Pdf){kind=link}
0 Comments