Brainscape's Knowledge GenomeTM

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


See full index

CSCI241 > Graphs terminology > Flashcards

Graphs terminology Flashcards

1
Q

Undirected graph

A

A non-empty graph where the edges do not have a specified direction

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

Directed graph (digraph)

A

A non-empty graph where the edges have a specified direction

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

Source

A

Digraph - where an edge starts

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

Sink

A

Digraph - where an edge ends

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

Subgraph

A

A subset of the vertices and edges in a graph

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

undirected -> directed

A

Assing a directionality, then give each edge an additional symetric edge

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

directed -> undirected

A

Remove the directionality of each edge, then remove duplicate edges

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

Weighted graph

A

Graph with real-valued weights assigned to the edges - stored instead of bools in adjacency list/matrix

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

Adjacency (undirected)

A

Two nodes are adjacent if they are connected by an edge

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

Adjacency (directed)

A

Node A is adjacent to node B if there is an edge from B to A.
Generally, a node is adjacent to another node if the first node has an inbound edge from the second node

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

Connected

A

(undirected) A path exists from every node to every other node

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

Weakly connected

A

(dircted) A path exists from every node to every other node ignoring directionality

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

Strongly connected

A

(directed) A path exists from every node to every other node taking directionality into account

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

Complete

A

Every node has an edge to every other node

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

Clique

A

A complete subgraph containing two or more nodes

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

Maximum clique

A

The largest clique of a given graph

17
Q

Maximal clique

A

A clique that is not a part of a larger clique

18
Q

Acyclic

A

A graph that does not contain any cycles (non-self loops)

19
Q

In-degree

A

(directed) The number of incoming edges to a node

20
Q

Out-degree

A

(directed) The number of outgoing edges from a node

21
Q

Reflexive

A

All nodes have self loops

22
Q

Irreflexive

A

No nodes have self loops

23
Q

Symmetric

A

(directed) All edges are reciprocated

24
Q

Anti-symmetric

A

(directed) No edge is reciprocated (does not exclude self loops)

25
Q

Transitive

A

If a path exists between two nodes, there must be an edge directly linking them

26
Q

path

A

The route(s) from one node to another

27
Q

Subpath

A

A section of a path

28
Q

Path length (weighted)

A

The combined/total weight/cost of traversing a given path

29
Q

Settled

A

Refers to Dijsktra’s: The shortest path to this node from the starting node has been found

30
Q

Frontier

A

Refers to Dijsktra’s: Just discovered this node, working on confirming the shortest path

31
Q

Unexplored

A

Refers to Dijsktra’s: The algorithm has not seen this node yet

CSCI241 (7 decks)

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