# Graphs Flashcards

What is the possible range of edges in a map, given the number of vertices (|V|)?

Between 0 and |V|^2 - |V|

When a graph considered complete?

If it has all possible (|V|^2 - |V|) edges.

What’s a digraph?

A directed graph.

What are weighted graphs?

Graphs whose edges have weights.

Edges may be incident to only one vertex.

False (minus edge-to-self graphs).

When is a subgraph maximally connected?

If none of its vertices connect to any vertices of its parent graph (which it doesn’t already contain).

Can a maximally connected subgraph have disconnected components?

No.

The maximally connected subgraphs of an directed graph are called connected components.

False - this is true for undirected graphs, whereas directed graphs call them strongly connected components.

Can an instance of a simple cycle also be a simple path?

No - due to the duplicate vertex (start and end).

What is the minimum number of vertices in a cycle?

3.

What determines the length of a path?

The number of edges (or vertices - 1).

What’s a DAG?

Directed Acyclic Graphs

Can a free tree be directed?

False.

Can a free tree have non-simple cycles?

Can’t have cycles at all.

Given a graph, what are the dimensions of its adjacency matrix?

|V| x |V|