Graph Theory Concepts Quiz

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is true about a connected graph with n vertices?

  • It contains exactly 1 cycle if there are n edges. (correct)
  • It has at least n edges and can contain multiple cycles.
  • It must be disconnected if n is greater than 1.
  • It must be acyclic and thus cannot have any edges.

If a binary tree has a height of h, how many leaves can it have at most?

  • h + 1
  • 2h
  • 2^h (correct)
  • h^2

In a tree with n > 1 vertices, how many leaves will it have at least?

  • n - 2
  • 1
  • 2 (correct)
  • n

How many leaves does any tree with maximum degree ∆ have at least?

<p>≥ ∆ leaves (D)</p> Signup and view all the answers

What is a spanning tree?

<p>A spanning subgraph that is also acyclic. (A)</p> Signup and view all the answers

If a graph is k-colorable, what does this imply?

<p>It can be colored using k colors without adjacent vertices sharing the same color. (D)</p> Signup and view all the answers

What defines a bipartite graph?

<p>It can be colored using 2 colors. (B)</p> Signup and view all the answers

What characterizes a vertex in a tree as a leaf?

<p>It has a degree of 1. (A)</p> Signup and view all the answers

What condition indicates that a connected graph G is Eulerian?

<p>All vertices in G have even degree. (D)</p> Signup and view all the answers

In a bipartite graph G = (X, Y, E), what is necessary for G to have a perfect matching?

<p>For all subsets A ⊆ (X ∪ Y ), the inequality |A| ≤ |N (A)| must hold. (C)</p> Signup and view all the answers

What can be deduced about a graph G with n ≥ 3 vertices if every vertex has degree at least n/2?

<p>G contains a Hamiltonian path. (B)</p> Signup and view all the answers

What is the independence number of a graph G, denoted by α(G)?

<p>The size of the largest independent set in G. (A)</p> Signup and view all the answers

What characterizes a tournament graph?

<p>It has at least one Hamiltonian path. (B)</p> Signup and view all the answers

What remains true about an Eulerian graph if one edge is removed?

<p>It will remain connected. (D)</p> Signup and view all the answers

In a k-regular bipartite graph, what is guaranteed?

<p>It has a perfect matching. (C)</p> Signup and view all the answers

If a graph G has an Eulerian circuit, what can be concluded about its edges?

<p>They can be partitioned into edge-disjoint cycles. (D)</p> Signup and view all the answers

What characterizes a set A as a subset of set B?

<p>Every element of A is also an element of B. (C)</p> Signup and view all the answers

Which of the following statements is true about event outcomes in a sample space?

<p>An event occurs if there exists an outcome in the sample space related to it. (B)</p> Signup and view all the answers

What is the definition of an edge in a graph?

<p>An edge connects two nodes in a set of edges. (C)</p> Signup and view all the answers

If sets S, T, and R are given, which of the following expresses a correct relationship?

<p>S , (T , R) is a subset of (S , T) ∪ R. (C)</p> Signup and view all the answers

What does the degree of a vertex in a graph represent?

<p>The total number of edges connected to that vertex. (D)</p> Signup and view all the answers

In the context of induction as a proof technique, what are the essential components?

<p>Base case, induction hypothesis, induction step. (C)</p> Signup and view all the answers

Which of the following statements about set operations is incorrect?

<p>S \ (T \ R) is disjoint from R. (C)</p> Signup and view all the answers

What does it mean for sets A and B if A ⊆ B and A ≠ B?

<p>A must be a proper subset of B. (A)</p> Signup and view all the answers

What does it mean for p to be a necessary condition for q?

<p>If p is false, then q must also be false (B), If q is true, then p must be true (D)</p> Signup and view all the answers

How is an even integer defined in terms of its prime factorization?

<p>An even integer is defined as n = 2k for some integer k (C)</p> Signup and view all the answers

What does the prime factorization theorem state?

<p>Every positive integer can be uniquely represented as a product of primes (D)</p> Signup and view all the answers

Which of the following correctly describes a prime integer?

<p>An integer greater than 0 that has exactly two distinct positive divisors (A)</p> Signup and view all the answers

If the sum of two integers is even, what can be concluded about their difference?

<p>Their difference is always even (C)</p> Signup and view all the answers

For any integer n, which statement is true if n is odd?

<p>n + n + 1 is always odd (C)</p> Signup and view all the answers

What is the inequality related to the factorial of n?

<p>n! &lt; n^n for all n &gt; 1 (B)</p> Signup and view all the answers

In the expression $X a(r^{n+1} - 1) = \frac{a_i}{r-1}$, what does it signify when $r \neq 1$?

<p>It indicates the sum of a geometric series (B)</p> Signup and view all the answers

What does the variance measure in statistics?

<p>How much a random variable deviates from its mean (B)</p> Signup and view all the answers

Which formula correctly represents the variance of a random variable X?

<p>V[X] = E[X^2] - E[X]^2 (D)</p> Signup and view all the answers

What does the standard deviation represent about a random variable?

<p>The variability around the mean (A)</p> Signup and view all the answers

In a directed graph, what do the vertices represent?

<p>The elements of a set (D)</p> Signup and view all the answers

How is the inverse of a relation R from set A to set B represented?

<p>R−1 = {(b, a)|(a, b) ∈ R} (D)</p> Signup and view all the answers

When two functions are considered equal, which of the following must be true?

<p>They have the same domain, codomain, and mapping (A)</p> Signup and view all the answers

In the context of directed graphs, what does an edge from vertex u to vertex u represent?

<p>A self-loop or reflexive relation (C)</p> Signup and view all the answers

Which statement about independent random variables X and Y is true?

<p>Their joint distribution can be expressed as the product of their individual distributions (B)</p> Signup and view all the answers

What is the correct definition of a function from set A to set B?

<p>A relation from A to B where each element in A maps to exactly one distinct element in B. (D)</p> Signup and view all the answers

Which of these statements about functions is true?

<p>If f and g are injective, then g â—¦ f is injective. (D)</p> Signup and view all the answers

Which of the following correctly describes equivalence relations?

<p>The intersection of two equivalence relations is guaranteed to be an equivalence relation. (B)</p> Signup and view all the answers

What does the range of a function f, denoted as Ran(f), represent?

<p>The set of all images b in B such that there exists an a in A with (a, b) in f. (A)</p> Signup and view all the answers

What characterizes a surjective function?

<p>Every element in the codomain B is an image of at least one element from domain A. (B)</p> Signup and view all the answers

What does it mean for a relation R on set A to be transitive?

<p>For any elements a, b, c in A, if (a,b) and (b,c) are in R, then (a,c) must also be in R. (A)</p> Signup and view all the answers

Which statement is true regarding the elements of an equivalence class?

<p>All elements in an equivalence class are related to each other by the relation R. (B)</p> Signup and view all the answers

Which property is NOT necessarily true for the intersection of two equivalence relations on set A?

<p>The intersection must contain all equivalence classes from both relations. (B)</p> Signup and view all the answers

Flashcards

Even Integer

An integer is even if it can be written as twice another integer.

Odd Integer

An integer is odd if it can be written as twice another integer plus 1.

Prime Number

A prime number is greater than 1 and has only two factors: 1 and itself.

Composite Number

A composite number is a positive integer greater than 1 and has at least one factor other than 1 and itself.

Signup and view all the flashcards

Sum of Odd Integers

The sum of the first n odd positive integers is equal to n².

Signup and view all the flashcards

Prime Factorization Theorem

Every positive integer can be uniquely represented as a product of prime numbers.

Signup and view all the flashcards

Divisible by k

k|n means that k divides n without leaving a remainder.

Signup and view all the flashcards

Necessary Condition

If p is a necessary condition for q, then the absence of p implies the absence of q, or equivalently, the presence of q implies the presence of p.

Signup and view all the flashcards

Subset

A set A is a subset of a set B if every element in A is also an element of B. We represent this with the notation A ⊆ B.

Signup and view all the flashcards

Proper Subset

A set A is a proper subset of a set B if A is a subset of B, but A is not equal to B. We represent this with the notation A ⊂ B.

Signup and view all the flashcards

Set Difference

Given two sets S and T, the set difference of S and T, denoted S \ T, contains all elements that are in S but not in T.

Signup and view all the flashcards

Graph

A graph is a structure consisting of a set of vertices (nodes) and a set of edges that connect pairs of vertices.

Signup and view all the flashcards

Edge

An edge in a graph connects two vertices. We say that an edge u, v ∈ E connects vertices u and v.

Signup and view all the flashcards

Adjacent Vertices

Two vertices are adjacent if they are connected by an edge. For example, u and v are adjacent if u, v ∈ E.

Signup and view all the flashcards

Degree of a Vertex

The degree of a vertex (node) is the number of edges incident to it, or the number of neighbors it has.

Signup and view all the flashcards

Induction

Induction is a proof technique used to prove a statement for all natural numbers. It involves proving a base case, an inductive hypothesis, and an inductive step.

Signup and view all the flashcards

Acyclic Graph

A graph with no cycles is called acyclic.

Signup and view all the flashcards

Internal Vertex vs. Leaf

A vertex of degree greater than 1 in a tree is called an internal vertex, otherwise it is called a leaf.

Signup and view all the flashcards

Spanning Subgraph

A spanning subgraph of a graph G is a subgraph with vertex set V(G).

Signup and view all the flashcards

Spanning Tree

A spanning subgraph that is a tree is called a spanning tree.

Signup and view all the flashcards

k-Colorable Graph

A graph is k-colorable if each vertex can be colored using one of the k colors so that adjacent vertices are colored using different colors.

Signup and view all the flashcards

Chromatic Number

The chromatic number of a graph G, χ(G), is the smallest value of k for which G is k-colorable.

Signup and view all the flashcards

Bipartite Graph

A bipartite graph is a graph that is 2-colorable.

Signup and view all the flashcards

Eulerian Graph

A graph where every vertex has an even degree.

Signup and view all the flashcards

Odd Graph

A graph where every vertex has an odd degree.

Signup and view all the flashcards

Hamiltonian Graph

A graph containing a cycle that includes every vertex.

Signup and view all the flashcards

Independent Set

A set of vertices where no two vertices are connected by an edge.

Signup and view all the flashcards

Independence Number of a Graph

The size of the largest independent set in a graph.

Signup and view all the flashcards

Dominating Set

A set of vertices where every vertex in the graph is either in the set or adjacent to a vertex in the set.

Signup and view all the flashcards

Clique

A set of vertices where every pair of vertices is connected by an edge.

Signup and view all the flashcards

Function from A to B

A relation from set A to set B where each element in A is associated with exactly one element in B.

Signup and view all the flashcards

Range of a function

The set of all elements in B that are mapped to by elements in A.

Signup and view all the flashcards

Symmetric Relation

A relation where for all elements a and b in set A, if (a, b) is in the relation, then (b, a) is also in the relation.

Signup and view all the flashcards

Transitive Relation

A relation where for all elements a, b, and c in set A, if (a, b) and (b, c) are in the relation, then (a, c) is also in the relation.

Signup and view all the flashcards

Antisymmetric Relation

A relation where for all elements a and b in set A, if (a, b) and (b, a) are in the relation, then a must equal b.

Signup and view all the flashcards

Partition of a set

A set of subsets of A where each element of A belongs to exactly one subset.

Signup and view all the flashcards

Equivalence Class

The set of all elements in A that are related to a given element a.

Signup and view all the flashcards

Bijective Function

A function that maps each element of A to a unique element of B and vice versa.

Signup and view all the flashcards

Expected Value (E[X])

The expected value of a random variable X is calculated by summing the product of each possible value of X and its corresponding probability.

Signup and view all the flashcards

Variance (V[X])

The variance of a random variable X measures how much the values of X deviate from its mean.

Signup and view all the flashcards

Standard Deviation (σ[X])

The standard deviation of a random variable X is the square root of its variance. It also measures the spread of values, but in the same units as the random variable.

Signup and view all the flashcards

Expected Value of Independent Random Variables

If two random variables X and Y are independent, then the expected value of their product is equal to the product of their expected values.

Signup and view all the flashcards

Directed Graph

A directed graph is a graph where edges have a direction. It consists of vertices and edges connecting them, with each edge pointing from one vertex to another.

Signup and view all the flashcards

Inverse of a Relation

The inverse of a relation R from A to B is a relation from B to A where the order of pairs is reversed.

Signup and view all the flashcards

Composition of Relations

The composition of two relations S and R, denoted S o R, combines the mapping of both relations into a single relation from A to C.

Signup and view all the flashcards

Equality of Functions

Two functions are equal if they have the same domain, codomain, and map the same elements in the domain to the same elements in the codomain.

Signup and view all the flashcards

Related Documents

CIS 160 Final Cheat Sheet PDF

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser