Graph Theory and Probability Flashcards

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/20

flashcard set

Earn XP

Description and Tags

Vocabulary flashcards covering core concepts in graph theory, directed graphs, probability fundamentals, and basic set theory.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

21 Terms

1
New cards

Complete Graph (K_n )

A graph with n vertices where every distinct pair of vertices is connected by an edge.

2
New cards

Path Graph (P_n)

path, line graph

3
New cards

Cycle Graph (C_n)

a graph which is a circle

4
New cards

Bipartite Graph

A graph whose vertices can be divided into two disjoint sets, U and V, such that every edge connects a vertex in U to one in V.

<p>A graph whose vertices can be divided into two disjoint sets, U and V, such that every edge connects a vertex in U to one in V.</p>
5
New cards

Definition of a Tree

A connected acyclic graph.

6
New cards

Cut Edge

An edge whose removal increases the number of connected components.

7
New cards

Graph Coloring

Assigning colors to vertices so no adjacent vertices have the same color.

8
New cards

Chromatic Number (\chi(G) )

The MINIMUM number of colors needed for a proper coloring of G.

9
New cards

Independent Set

A set of vertices where no two vertices are adjacent.

10
New cards

Clique

A subset of vertices where every two distinct vertices are adjacent (i.e., a complete subgraph).

11
New cards

Strong Connectivity

For any two vertices u, v, there's a directed path from u to v AND from v to u.

12
New cards

Strongly Connected Component (SCC)

A maximal set of vertices in which every pair is mutually reachable.

13
New cards

Reduced Graph (Condensation Graph)

A DAG formed by contracting each SCC into a single vertex.

14
New cards

Directed Acyclic Graph (DAG)

A directed graph with no directed cycles.

15
New cards

Topological Sort

A linear ordering of DAG vertices such that for every edgeu \rightarrow v, u comes before v.

16
New cards

Probability Space (\Omega )

The set of all possible outcomes of an experiment.

17
New cards

Uniform Probability Space

All outcomes are equally likely. P(\omega) = 1/|\Omega| .

18
New cards

Event (in Probability)

A subset of the sample space \Omega .

19
New cards

Conditional Probability P(A|B)

"Probability of A given B": P(A|B) = \frac{P(A \cap B)}{P(B)}, if P(B) > 0.

20
New cards

Independent Events (A and B)

P(A \cap B) = P(A)P(B) . Equivalently: P(A|B)=P(A) if P(B)>0)

21
New cards

Power Set 2^A)

The set of all subsets of A.