Basics of Graph Theory: Graphs and Terminologies
30 Questions
1 Views

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

A __________ graph is a simple graph in which the set of vertices can be partitioned into two sets X and Y such that every edge is between a vertex in X and a vertex in Y

Bipartite

Complete ________ Graph Km,n has m vertices in X and n vertices in Y with an edge between every vertex in X and every vertex in Y

Bipartite

The graph resulting from replacing each arc of a digraph with an edge is called the underlying ________

Graph

The ________ of a complete graph is called a Tournament

<p>Orientation</p> Signup and view all the answers

A ________ graph is a graph with at least one edge and at least one arc

<p>Mixed</p> Signup and view all the answers

Two graphs are ________ if their sets of vertices and edges are identical

<p>Identical</p> Signup and view all the answers

A graph with no loops is called a ______

<p>simple graph</p> Signup and view all the answers

Two or more edges that join the same pair of distinct vertices are called ______

<p>parallel edges</p> Signup and view all the answers

A graph with at least one loop is called a ______

<p>pseudograph</p> Signup and view all the answers

A vertex of a graph that is not an end of any edge is an ______ vertex

<p>isolated</p> Signup and view all the answers

A graph that is in one piece, where each vertex can be reached from all other vertices, is called a ______ graph

<p>connected</p> Signup and view all the answers

A graph without any edges is known as a ______ graph

<p>null</p> Signup and view all the answers

A simple graph with two vertices may have ______ edge or one edge.

<p>no</p> Signup and view all the answers

Any simple graph with three vertices gives rise to ______ non-isomorphic cases.

<p>four</p> Signup and view all the answers

Cyclic Graph Cn = (V, E) (where n > 2) is a graph isomorphic to a graph with V = {v1, v2,..., vn} and E = {{v1, v2}, {v2, v3},..., {vn−1, vn}, {vn, v1}}. Triangle is a cyclic graph with ______ vertices.

<p>three</p> Signup and view all the answers

The trivial graph is the only graph of order ______.

<p>one</p> Signup and view all the answers

A graph H = (W, F) is a Subgraph of the graph G = (V, E) if W is a subset of V, and F is a subset of E. Cycle in G - If a subgraph of H of the graph G is a ______ graph.

<p>cyclic</p> Signup and view all the answers

Clique in G - A complete subgraph of G. Supergraph of G - Any graph G′ for which a given graph G is a ______.

<p>subgraph</p> Signup and view all the answers

The spanning subgraph obtained by deleting the edges of F from G is denoted by G − ______.

<p>F</p> Signup and view all the answers

If F consists of one edge f, write G − ______.

<p>f</p> Signup and view all the answers

The graph obtained from G by deleting every vertex in W as well as any edge in E that is adjacent to the vertices in W is denoted by G − ______.

<p>W</p> Signup and view all the answers

If W consists of a single vertex w, write G − ______.

<p>w</p> Signup and view all the answers

A subgraph G′ of G is a Vertex-Induced Subgraph if there exists a set W of vertices in G such that ⟨W⟩ = ______.

<p>G'</p> Signup and view all the answers

A subgraph G′ of G is an Edge-Induced Subgraph if there exists a set F of edges in G such that ⟨F⟩ = ______.

<p>G'</p> Signup and view all the answers

A vertex v is an isolated vertex if d(v)=0. A vertex v is an end vertex if d(v) = ______

<p>0</p> Signup and view all the answers

A graph is k-Regular if the degree of each vertex is ______

<p>k</p> Signup and view all the answers

A graph is Regular if there exists a nonnegative integer k that it is ______-regular.

<p>k</p> Signup and view all the answers

Conjecture: Given the graph G with size ε ε is the number of edges in G 2ε is the total degree of the vertices in G. A vertex in a graph is an Odd Vertex if the degree is ______

<p>odd</p> Signup and view all the answers

In a digraph, the sum of the outdegrees of all vertices is equal to the number of arcs, which is also equal to the sum of all indegrees of all vertices. Indegree (d−(v)) of that vertex - the number of arcs adjacent to a vertex Outdegree (d+(v)) of that vertex - the number of arcs adjacent from a vertex. This is known as the ______

<p>degree-sum theorem</p> Signup and view all the answers

The adjacency matrix of a simple graph is a binary matrix (0, 1) matrix in which each diagonal entry is ______

<p>zero</p> Signup and view all the answers

More Like This

Use Quizgecko on...
Browser
Browser