Graph Theory

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

1/32

flashcard set

Earn XP

Description and Tags

This is called a graph

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

33 Terms

1
New cards

Digraph

A directed graph

2
New cards

Simple

  • Undirected

  • Unweighted

  • No arcs

  • No loops

3
New cards

Arc

Two edges connect two vertices

4
New cards

Closed Walk

Starts and ends at the same vertex (eg. A-B-A)

5
New cards

Open Walk

Starts and ends at different vertices (eg. A-B-C)

6
New cards

Path

Walk with no repeat edges or vertices

7
New cards

Closed Path

Walk that repeats no edges or vertices except the initial vertex, ends at initial vertex (eg. A-B-C-D-A)

8
New cards

Open Path

Walk with no repeat edges or vertices, must end at a different place to starting (eg. A-B-C)

9
New cards

Length

Amount of edges crossed

10
New cards

Trail

A walk with no repeated edges but vertices can be repeated. Can be open or closed

11
New cards

Connected

When undirected, if two vertices are joined by any combination of edges

12
New cards

Strongly connected

Each vertex is connected there and back

13
New cards

Weakly connected

Directed graph in which, if undirected, graph would be connected, but direction means some points cannot be reached by path from other vertex

14
New cards

Complete Graph

  • Simple

  • Connected to every other vertex

  • No multiple edges

15
New cards

Adjacent Vertices

Vertices directly joined by an edge

16
New cards

Bridge

An edge in a connected graph that, if removed, would make the graph disconnected

17
New cards

Planar

Can be drawn in the 2-d plane without crosses

18
New cards

Euler’s Rule

V + F = E + 2

19
New cards

Subgraph

A selection of vertices and edges of a larger graph

20
New cards

Tree

Connected graph with no cycles

21
New cards

Cycle

Closed path

22
New cards

Bipartite Graph

Can be split into two groups where every edge connects from one group to another, and no edge connects within a group

23
New cards

Complete bipartite graph

When every vertex in one group connects to all of the vertices in the other group

24
New cards

A complete bipartite graph is

not a complete graph

25
New cards

Degree/ Order

If undirected, the number of edges connected to a vertex

26
New cards

Odd vertex

A vertex with an odd degree

27
New cards

Even vertex

A vertex with an even degree

28
New cards

In degree

Connected into a vertice

29
New cards

Out degree

Directed from a vertice

30
New cards

Eulerian Trail

A closed trail with no odd vertices

31
New cards

Semi-eulerian trail

An open trail with exactly two odd-degree vertices

32
New cards

Hamiltonian Path

A closed path that visits every vertex only once and uses no edge more than once

33
New cards

Semi-hamiltonian path

An open path that visits every vertex only once and uses no edge more than once