Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Decision 1 > Graphs And Networks > Flashcards

Graphs And Networks Flashcards

1
Q

What is a graph?

A

A graph consists of vertices/nodes which are connected by edges/arcs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a network/ weighted graph?

A

When graph has a number associated with each edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a degree/valance/order of a vertex?

A

Number of edges connected to vertex/node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a path?

A

Sequence of edges. In which no vertex appears more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a walk?

A

A path in which you are permitted to return to vertices more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a cycle?

A

A closed path that forms a loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a trail?

A

A walk where no arcs are repeated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a loop?

A

Starts and finishes at the same point

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a simple graph?

A

No loops, not more than one edge connecting a pair of vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a Eulerian graph?

A

Each node has an even number of edges connected to it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a semi-eulerian graph

A

Graph that consists of 2 nodes with odd valency and the rest are even

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a eulerian cycle?

A

Cycle that covers every arc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a eulerian graph?

A

No odd nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is a Hamiltonian cycle?

A

Cycle that covers every node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a tree?

A

Connected graph with no cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a spanning tree?

A

Subgraph which includes all the vertices of a graph and is also a tree

17
Q

What is a bipartite graph?

A

Consists of 2 sets of vertices. The edges only join vertices in C to vertices in Y

18
Q

What is a complete graph?

A

Graph in which every vertex is directly connected by an edge to each other vertex.

19
Q

What is a complete bipartite graph?

A

Graph in which there are r vertices in set X and s vertices in set Y (K s,r)

20
Q

What is an isomorphic graph?

A

Shows the same info but drawn differently

21
Q

What is a minimum spanning tree?

A

Connected graph with no cycles that includes all vertices. It also has the minimum weight

Decision 1 (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions