Unit 5 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes


Unit 5 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes

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:  P ( n , r ) = n ! / ( n r ) !
    - Combinations: Selection of objects without considering the order.
      - Formula:  n C r = n ! / r ! ( n r ) !

    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