DAY 2 JUNE | GRAPH CSE 103

 SLIDE -1

Path and simple path:

✅ Example: A → B → C → D is a simple path.
❌ A → B → A → C is not a simple path (A is repeated).


In a Directed Graph

There are two types of degrees:

  • In-degree: Number of edges coming into the vertex.

  • Out-degree: Number of edges going out from the vertex.


Graph G:
  1 — 2      4 — 5
             |
             6
This graph has 2 connected components:

Component 1: {1, 2}

Component 2: {4, 5, 6}

 Number of edges in a complete graph:

If a complete graph has n vertices, then the number of edges is:

Edges=n(n−1)2\text{Edges} = \frac{n(n-1)}{2}



Vertices and Edges

This is a directed graph (also called a digraph) where:

  • Nodes (like A, B, C...) are vertices.

  • Arrows between them are directed edges (they show direction).

🔹 Adjacent

  • Two vertices are adjacent if there is an edge directly connecting them.

  • Example: If there's an arrow from A → B, then A is adjacent to B.

🔹 Successor

  • If A → B, then B is the successor of A.

  • Means: from A, you can go directly to B.

🔹 Predecessor

  • If A → B, then A is the predecessor of B.

  • Means: B can be reached directly from A.


What is a Bipartite Graph (in simple words)?

A bipartite graph is a graph where:

You can split all the nodes into two groups so that edges only connect nodes from different groups, never within the same group.

Use 2 colors:

  • Try to color the graph with 2 colors (say Red & Blue) so that no two connected nodes have the same color.

  • If you can do this → the graph is bipartite.

 A COMPLETE BIPARTITE GRAPH :

Number of edges in K<sub>m,n</sub>:

Total edges=m×n\text{Total edges} = m \times n

Comments

Post a Comment

Popular posts from this blog

Phy 129 - WM, CT-03

  Statement : For position ( x x x ) and momentum ( p p p ), the uncertainty principle is: Δ x ⋅ Δ p ≥ ℏ 2 \Delta x \cdot \Delta p \geq \frac{\hbar}{2} Δ x ⋅ Δ p ≥ 2 ℏ ​ where Δ x \Delta x Δ x is the uncertainty in position, Δ p \Delta p Δ p is the uncertainty in momentum, and ℏ ≈ 1.05 × 1 0 − 34   J \cdotp s \hbar \approx 1.05 \times 10^{-34} \, \text{J·s} ℏ ≈ 1.05 × 1 0 − 34 J \cdotp s . Similarly, for energy ( E E E ) and time ( t t t ): Δ E ⋅ Δ t ≥ ℏ 2 \Delta E \cdot \Delta t \geq \frac{\hbar}{2} Δ E ⋅ Δ t ≥ 2 ℏ ​ . #Learning -2 p = γ m v p = \gamma m v p = γm v , where: m m m is the rest mass of the particle, v v v is the velocity of the particle, γ \gamma γ is the Lorentz factor, given by γ = 1 1 − v 2 c 2 \gamma = \frac{1}{\sqrt{1 - \frac{v^2}{c^2}}} ; A wave group: a wave group corresponds to a moving particle and is formed by the superposition of multiple harmonic waves with different frequencies, wave numbers, and amplitudes.\ Wave Function Ψ ( x ) \Psi(x)...
Read more
Copy of Jujutsu Kaisen 2D Game UI Design Request                                                                                                                                                                ...
Read more

Online 3 CSE 102; Array Resources.

 Problems and their solution: Practice Problems on “Array” (MOODLE) Problem 1: Floor, Ceil within an array              A[] = {96, 21, 58, 34, 46} Number Floor Ceil 15 -1 21 21 21 21 30 21 34 96 96 96 98 96 -1 Solution: Sort them, then find floor and ceil from the array. Use selection sort: void selectionSort(int arr[], int n) {     int i, j, minIndex, temp;     for (i = 0; i < n - 1; i++) {         minIndex = i;         // Find the index of the smallest element in the remaining array         for (j = i + 1; j < n; j++) {             if (arr[j] < arr[minIndex])                 minIndex = j;         }         // Swap the found minimum element with the first element         if (minIndex != i) {    ...
Read more