decision terminology

5.0(1)
studied byStudied by 4 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/24

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

25 Terms

1
New cards

algorithm

finite sequence of step by step instructions carried out to solve a problem

2
New cards

order (of an algorithm)

a function of the size of the algorithm

3
New cards

subgraph

a graph where all of the vertices and edges belong to the original graph

4
New cards

degree/valency/order

the number of edges attached to a vertex

5
New cards

walk

finite sequence of edges where the end vertex of one edge is the start vertex of another

6
New cards

path

a walk in which no vertex is visited more than once

7
New cards

trail

a walk in which no edge is visited more than once

8
New cards

cycle

a walk where the end vertex is the same as the start vertex and no other vertex is visited more than once

9
New cards

hamiltonian cycle

a cycle that includes every vertex

10
New cards

loop

an edge that starts and finishes at the same vertex

11
New cards

simple graph

no loops or multiple edges

12
New cards

Euler’s handshaking lemma

sum of degrees of vertices = 2 x number of edges

13
New cards

tree

connected graph with no cycles

14
New cards

spanning tree

subgraph which is also a tree

15
New cards

complete graph

a graph where every vertex is connected to every other vertex with one edge

16
New cards

isomorphic graphs

graphs which display the same information but are drawn differently

17
New cards

adjacency matrix

describes the number of arcs between vertices

18
New cards

distance matrix

describes the weight of arcs between vertices

19
New cards

planar graph

can be drawn in a plane such that no two edges meet except at a vertex

20
New cards

Eulerian graph

trail that includes every edge, starts and finishes at the same vertex, and has only even vertices

21
New cards

Semi-Eulerian graph

trail that includes every edge, but starts and finishes at different vertices, and has exactly two odd vertices

22
New cards

tour

a walk which visits every vertex and returns to its starting vertex

23
New cards

classical problem

each vertex is visited exactly once before returning to the start

24
New cards

practical problem

each vertex is visited at least once before returning to the start

25
New cards

difference between Dijkstra’s and Floyd’s

Dijkstra’s finds the shortest path between two vertices, Floyd’s finds the shortest path between every pair of vertices