SWEN2006 Lecture Graph Theory

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

1/32

flashcard set

Earn XP

Description and Tags

Flashcards on Graph Theory based on lecture notes.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

33 Terms

1
New cards

What are the different types of graphs?

Simple graphs, Multigraphs, Pseudographs, Directed graphs, Directed multigraphs

2
New cards

What is a Simple Graph?

A graph G = (V, E) consisting of V, a non-empty set of vertices and E, a set of unordered pairs of distinct elements of V called edges.

3
New cards

Give some application examples of Graph Models

Social networks, Transportation systems, Network topology, Biological systems, Knowledge Graphs

4
New cards

What is the degree of a vertex in an undirected graph?

The number of edges incident with it, except that a loop at a vertex contributes twice to the degree of the vertex.

5
New cards

What is an isolated vertex?

A vertex of degree 0.

6
New cards

What is a pendant vertex?

A vertex which has degree 1.

7
New cards

What is the Handshaking Theorem?

The sum of the degrees of the vertices is twice the number of edges.

8
New cards

What does Theorem 2 state about an undirected graph?

An undirected graph has an even number of vertices of odd degree.

9
New cards

What is the in-degree of a vertex v in a directed graph?

The number of edges with v as their terminal vertex.

10
New cards

What is the out-degree of a vertex v in a directed graph?

The number of edges with v as their initial vertex.

11
New cards

What does Theorem 3 state about a direct graph, G = (V,E)?

The sum of the in-degrees and the sum of the out-degrees are equal and both sums are the number of edges in the graph.

12
New cards

What is a Complete graph of n vertices, denoted Kn?

A simple graph that contains exactly one edge between each pair of distinct vertices.

13
New cards

How is a wheel Wn obtained?

Adding a vertex to the cycle Cn for n ≥ 3, and connecting this new vertex to each of the n vertices of Cn.

14
New cards

What is a Bipartite Graph?

A simple graph G in which its vertices V are partitioned into two disjoint sets V1 and V2 such that there is an edge between every vertex in V1 and a vertex in V2 (and no edge in G connects either two vertices in V1 or two vertices in V2).

15
New cards

What is a Complete Bipartite Graph?

Has its vertices partitioned in two disjoint sets m and n such that every vertex in m is connected to every vertex in n by an edge.

16
New cards

What is the theorem that determines if a simple graph is bipartite?

A simple graph is bipartite if and only if it is possible to assign one of two different colours to each vertex of the graph so that no two adjacent vertices are assigned the same colour.

17
New cards

What is a matching in a simple graph?

A subset of the set of edges of the graph such that no two edges are incident with the same vertex.

18
New cards

What is a maximum matching?

A matching with the largest number of edges.

19
New cards

What is a maximal matching?

A matching where all the vertices are matched.

20
New cards

What is Graph Colouring?

Assignment of a colour to each vertex of the graph so that no two adjacent vertices are the same colour.

21
New cards

What is the chromatic number of a graph?

The least number of colours needed for a colouring of that graph.

22
New cards

What is the adjacency matrix A of G?

The zero-one matrix with 1 as its (i, j)th entry when vi, vj are adjacent, and 0 as its (i, j)th when they are not adjacent.

23
New cards

What is a Path?

A sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph.

24
New cards

What is a circuit?

Begins and ends at the same vertex, that is, if u = v, and has length greater than zero.

25
New cards

What is a simple path or circuit?

It does not contain the same edge more than once.

26
New cards

When is an undirected graph called connected?

There is a path between every pair of distinct vertices in the graph.

27
New cards

What is an Euler circuit in a graph G?

A simple circuit containing every edge of G.

28
New cards

What is an Euler path in a graph G?

A simple path containing every edge of G.

29
New cards

What is the requirement for a connected multigraph to have an Euler circuit?

Each of its vertices has even degree.

30
New cards

What is the requirement for a connected multigraph to have an Euler path but not an Euler circuit?

It has exactly two vertices of odd degree.

31
New cards

What is a Hamilton Path?

A simple path in a graph G that passes through every vertex exactly once.

32
New cards

What is a Hamilton circuit?

A simple circuit in a graph G that passes through every vertex exactly once

33
New cards

What can we find using Dijkstra’s Algorithm?

We can find the length of the shortest path between two vertices of a weighted graph.