Scribd
Upload
352 views176 pages

Graph Theory Notes

The document outlines the syllabus for the Graph Theory course (BCS405B) for the IV Semester B.E. in Computer Science and Engineering at Akash Institute of Engineering & Technology. It includes course objectives, teaching-learning processes, detailed modules covering various graph concepts, assessment details, and suggested learning resources. The course aims to equip students with fundamental graph concepts, problem-solving skills, and real-world applications in computer science engineering.

Uploaded by

acchugowdaarchana
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
352 views176 pages

Graph Theory Notes

The document outlines the syllabus for the Graph Theory course (BCS405B) for the IV Semester B.E. in Computer Science and Engineering at Akash Institute of Engineering & Technology. It includes course objectives, teaching-learning processes, detailed modules covering various graph concepts, assessment details, and suggested learning resources. The course aims to equip students with fundamental graph concepts, problem-solving skills, and real-world applications in computer science engineering.

Uploaded by

acchugowdaarchana
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

AKASH INSTITUTE OF ENGINEERING & TECHNOLOGY

Affiliated to Visvesvaraya Technological University, Belagavi and Approved by AICTE, New Delhi
Devanahalli, Bengaluru- 562110, [Link]

DEPARTMENT OF MATHEMATICS

STUDY MATERIAL

COURSE: GRAPH THEORY


COURSE CODE: BCS405B
CLASS: IV Semester

VISVESVARAYA TECHNOLOGICAL UNIVERSITY, BELAGAVI


B.E. in Computer Science and Engineering

Scheme of Teaching and Examinations 2022

Outcome-Based Education (OBE) and Choice Based Credit System (CBCS)

(Effective from the academic year 2022 - 23)


COURSE SYLLABUS
GRAPH THEORY Semester IV
Course Code BCS405B CIE Marks 50
Teaching Hours/Week (L:T:P: S) [Link] SEE Marks 50
Total Hours of Pedagogy 40 Total Marks 100
Credits 03 Exam Hours 03
Examination type (SEE) Theory

Course objectives:
● Understand the basic concepts of graphs and their properties, and operations of graphs.
● Hamiltonian and Euler graphs, trees and matrix representation of the graph.
● Apply the concepts of a planar graph, matching and colouring in computer science
engineering.

Teaching-Learning Process
Pedagogy (General Instructions):
These are sample Strategies, teachers can use to accelerate the attainment of the various course outcomes.
1. In addition to the traditional lecture method, different types of innovative teaching methods may
be adopted so that the delivered lessons shall develop students’ theoretical and applied
Mathematical skills.
2. State the need for Mathematics with Engineering Studies and Provide real-life examples.
3. Support and guide the students for self–study.
4. You will assign homework, grading assignments and quizzes, and documenting students'
progress.
5. Encourage the students to group learning to improve their creative and analytical skills.
6. Show short related video lectures in the following ways:
● As an introduction to new topics (pre-lecture activity).
● As a revision of topics (post-lecture activity).
● As additional examples (post-lecture activity).
● As an additional material of challenging topics (pre-and post-lecture activity).
● As a model solution for some exercises (post-lecture activity).

Module-1
Introduction to Graphs: Introduction- Basic definition – Application of graphs – finite, infinite and
bipartite graphs – Incidence and Degree – Isolated vertex, pendant vertex and Null graph. Paths and
circuits – Isomorphism, sub-graphs, walks, paths and circuits, connected graphs, disconnected graphs
and components. (8 hours)
(RBT Levels: L1, L2 and L3)
Teaching-Learning Chalk and talk method / PowerPoint Presentation
Process
Module-2
Eulerian and Hamiltonian graphs: Euler graphs, Operations on graphs, Hamiltonian paths and circuits,
Travelling salesman problem. Directed graphs – types of digraphs, Digraphs and binary relation.
(8 hours)
(RBT Levels: L1, L2 and L3)

Teaching-Learning Process Chalk and talk method / PowerPoint Presentation


Module-3

@# 4
Trees – properties, pendant vertex, Distance and centres in a tree - Rooted and binary trees, counting
trees, spanning trees.
Connectivity Graphs: Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices,
Fundamental circuits. (8 hours)
(RBT Levels: L1, L2 and L3)
Teaching-Learning Chalk and talk method / PowerPoint Presentation
Process
Module-4
Planar Graphs: Planar graphs, Kuratowski’s theorem (proof not required), Different
representations of planar graphs, Euler's theorem, Geometric dual.
Graph Representations: Matrix representation of graphs-Adjacency matrix, Incidence Matrix, Circuit
Matrix, Path Matrix. (8 hours)
(RBT Levels: L1, L2 and L3)
Teaching-Learning Process Chalk and talk method / PowerPoint Presentation
Module-5:
Graph Colouring: Colouring- Chromatic number, Chromatic polynomial, Matchings, Coverings, Four
colour problem and Five colour problem. Greedy colouring algorithm. (8 hours)
(RBT Levels: L1, L2 and L3)
Teaching-Learning Process Chalk and talk method / PowerPoint Presentation
Course outcome (Course Skill Set)
At the end of the course, the student will be able to:
1. Explain the fundamental concepts of properties and representation of graphs.
2. Solve the problems involving characterization and operations on graphs.
3. Apply concepts of trees and graph connectivity to solve real world problems.
4. Apply the concepts of planar graph and graph representations to solve the given problem.
5. Use the concepts of matching and coloring of graphs to solve the real world problems.
Assessment Details (both CIE and SEE)
The weightage of Continuous Internal Evaluation (CIE) is 50% and for Semester End Exam (SEE) is 50%.
The minimum passing mark for the CIE is 40% of the maximum marks (20 marks out of 50) and for the
SEE, the minimum passing mark is 35% of the maximum marks (18 out of 50 marks). The student is
declared as a pass in the course if he/she secures a minimum of 40% (40 marks out of 100) in the sum
total of the CIE (Continuous Internal Evaluation) and SEE (Semester End
Examination) taken together.

Continuous Internal Evaluation:


● There are 25 marks for the CIE's Assignment component and 25 for the Internal Assessment Test
component.
● Each test shall be conducted for 25 marks. The first test will be administered after 40-50% of the
coverage of the syllabus, and the second test will be administered after 85-90% of the coverage of
the syllabus. The average of the two tests shall be scaled down to 25 marks
● Any two assignment methods mentioned in the 22OB2.4, if an assignment is project-based then
only one assignment for the course shall be planned. The schedule for assignments shall be planned
properly by the course teacher. The teacher should not conduct two assignments at the end of the
semester if two assignments are planned. Each assignment shall be conducted for 25 marks. (If two
assignments are conducted then the sum of the two assignments shall be scaled down to 25 marks)
The final CIE marks of the course out of 50 will be the sum of the scale-down marks of tests and
assignment/s marks.

@# 5
Internal Assessment Test question paper is designed to attain the different levels of Bloom’s
taxonomy as per the outcome defined for the course.
Semester-End Examination:
Theory SEE will be conducted by the University as per the scheduled timetable, with common
question papers for the course (duration 03 hours).
1. The question paper will have ten questions. Each question is set for 20 marks.
2. There will be 2 questions from each module. Each of the two questions under a module (with a
maximum of 3 sub-questions), should have a mix of topics under that module.
3. The students have to answer 5 full questions, selecting one full question from each module.
Marks scored shall be proportionally reduced to 50 marks
Suggested Learning Resources:
Books (Name of the author/Title of the Book/Name of the publisher/Edition and Year) Text
Books:
1. Narsingh Deo, Graph theory with the applications to engineering & Computer Science,
Dovers Publications, 2016
2. J.A. Bondy and U.S.R. Murty. Graph theory with Applications, Springer, 1st edition, 2008.
Reference Books:
1. Garry Chartand and Ping Zhang, Introduction to Graph Theory, Tata McGraw-Hill, 2006.
2. Frank Harary, Graph Theory, Narosa Publishing House, Latest edition.
3. R. Diestel, Graph Theory, free online edition, 2016: [Link]/[Link].
4. Douglas B. West, Introduction to Graph Theory, Prentice Hall India Ltd.,2001
5. Robin J. Wilson, Introduction to Graph Theory, Longman Group Ltd.,2010
Web links and Video Lectures (e-Resources):
• [Link]
• [Link]
• [Link]
• VTU e-Shikshana Program
• VTU EDUSAT Program.

Activity-Based Learning (Suggested Activities in Class)/Practical-Based Learning


• Quizzes
• Assignments
• Seminar

Department of Mathematics, AIET i


MODULE-1
GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


MODULE-2
GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


MODULE-3
GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


MODULE-4 & 5
GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET


GRAPH THEORY

Department of Mathematics, AIET

Common questions

Powered by AI

Understanding the properties of trees is crucial because they represent hierarchical structures, vital for algorithms and data organization in computing. Trees are used in data structures like binary search trees, heap structures, and for routing algorithms. Rooted trees and spanning trees are essential for network design and resource allocation, providing efficient optimization techniques for searching and minimizing paths .

The Travelling Salesman Problem exemplifies the complexities inherent in determining Hamiltonian paths due to its NP-hard nature, demanding a minimal path through each city (vertex) in a weighted directed graph exactly once. The challenge lies in computing an efficient route with minimal cost, given its factorial growth in complexity as the number of vertices increases. TSP highlights the computational limits and explores approximation and heuristic solutions in real-world applications like logistics and route optimization .

Bipartite graphs, consisting of two separate sets of vertices with edges only between sets, form the foundation for solving problems in graph matching. This relationship allows for identifying maximum matching, pairing vertices such as job assignments or network connections optimally. Bipartite graphs facilitate the use of algorithms like the Hungarian algorithm to find perfect matches, making them instrumental for scheduling, resource allocation, and network designs .

Hamiltonian graphs contain a Hamiltonian circuit, which is a cycle that visits every vertex exactly once, whereas Eulerian graphs contain an Eulerian circuit that uses every edge of the graph exactly once. While a Hamiltonian graph's existence requires visiting vertices, an Eulerian graph focuses on edges. Additionally, a connected graph has an Eulerian circuit if the degree of all vertices is even and possesses a Hamiltonian circuit if certain sufficient conditions related to vertex degrees are met .

Matrix representations such as adjacency, incidence, and circuit matrices provide systematic methods to analyze graph properties like connectivity, paths, and circuits. An adjacency matrix efficiently shows direct connections between vertices, aiding in identifying possible paths and circuits. An incidence matrix helps in analyzing and solving problems related to edge and vertex configurations. These matrices democratize complex graph algorithms by simplifying computations related to graph traversals and connectivity .

The Four Color Theorem, stating that any planar graph can be colored with no more than four colors without adjacent regions sharing the same color, has both theoretical and practical implications. Theoretically, it advances the understanding of graph colorability and challenges in combinatorial problem solving. Practically, it is applicable to problems in scheduling, map coloring, and resource allocation, where it ensures optimal utilization of limited resources while preventing conflicts like adjacent resource overlaps .

Planar graphs are pivotal in computer science for solving problems such as network circuit design and geographical mapping. Their use is prominent due to their property of being drawable on a plane without crossing edges, which helps in visualizing networks and optimizing layouts. By applying concepts like Euler's theorem and Kuratowski’s theorem, one can determine graph planarity, which aids in minimizing cross-links in various applications such as VLSI design and urban planning .

Cut sets and cut vertices are pivotal in assessing graph connectivity by identifying points and edges whose removal increases the number of disconnected components. Understanding these components aids in determining graph resilience and vulnerability. Cut vertices can pinpoint critical points in a network where failure could disrupt communication, while cut sets find redundant pathways, making them valuable for network design and error-proofing .

The greedy coloring algorithm provides efficient solutions by iteratively assigning the first available color to a vertex, ensuring no two adjacent vertices share the same color. Although not always providing the optimal minimum number of colors, it efficiently approaches the chromatic number for large graphs, especially in sparse applications. This makes it valuable in network frequency assignments and optimizing resource allocations where a quick heuristic can suffice .

Vertex and edge connectivity are fundamental for designing robust networks by indicating the minimum number of vertices or edges that need removal to disconnect the network. High connectivity implies redundancy, improving fault tolerance and ensuring reliable communication. In designing reliable network infrastructures, high vertex and edge connectivity are prioritized to avoid single points of failure and maintain service continuity even during partial network disruptions .

You might also like