Unit 5 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes
Graphs
- A collection of vertices (or nodes) and edges that connect pairs of vertices.
- Terminology:
- Vertex: A point in the graph.
- Edge: A line connecting two vertices.
- Degree of a Vertex: The number of edges connected to a vertex.
- Loop: An edge that connects a vertex to itself.
- Path: A sequence of vertices connected by edges.
- Cycle: A path that begins and ends at the same vertex.
Representation of Graphs
- Adjacency Matrix: A matrix where each cell indicates if an edge exists between vertex pairs.
- Adjacency List: A list where each vertex stores a list of adjacent vertices.
Multigraphs
- A graph that can have multiple edges between the same pair of vertices.
- Key Characteristics: Allows loops and multiple edges, used in complex network modeling.
Bipartite Graphs
- A graph whose vertices can be divided into two disjoint sets such that edges only connect vertices from different sets.
- Application: Common in matching problems, like job assignments.
Planar Graphs
- A graph that can be drawn on a plane without edges crossing.
- Euler’s Formula: For planar graphs, V - E + F = 2 where V is vertices, E is edges, and F is faces.
Isomorphism and Homeomorphism of Graphs
- Isomorphism: Two graphs are isomorphic if they have identical structure.
- Homeomorphism: Graphs are homeomorphic if they can be transformed into each other by adding or removing vertices of degree 2.
Euler and Hamiltonian Paths
- Euler Path: A path that visits every edge exactly once.
- Hamiltonian Path: A path that visits every vertex exactly once.
Graph Coloring
- Assigning colors to vertices so that no two adjacent vertices have the same color.
- Applications: Scheduling, register allocation in compilers.
Combinatorics
- The branch of mathematics dealing with counting, arrangement, and combination of objects.
- Applications: Used in computer science for algorithm analysis, probability, and optimization.
Counting Techniques
- Fundamental Principle of Counting: If one event has m outcomes and a second event has n outcomes, the total is m x n.
- Permutations: Arrangements of objects in a specific order.
- Formula:
- Combinations: Selection of objects without considering the order.
- Formula:
Pigeonhole Principle
- If n items are put into m containers, and n > m , at least one container must contain more than one item.
- Applications: Used in problems involving repetition, such as ensuring duplicate items in subsets.
No comments:
Post a Comment