Shared Flashcard Set

Details

Discrete Mathematics (Final)
Definitions for the final in discrete math
37
Computer Science
Undergraduate 2
12/05/2007

Additional Computer Science Flashcards

 


 

Cards

Term
Domain
Definition
All possible values for X
Term
Co-Domain
Definition
Possible Y (results)
Term
Range
Definition
Actual (Y) Results
Term
One-to-one function
Definition
Every X goes to a unique Y
Term
Onto function
Definition

Every Y is used

 

(*range = co-domain)

Term
Graph
Definition
Consists of a finite set of vertices (nodes) and a finite set of edges (lines) connecting them.
Term
Directed Graph (Di-Graph)
Definition
A graph where each edge is associates with an ordered pair of vertices (nodes)
Term
Simple Graph
Definition
A graph that does not have any loops or parallel edges
Term
Complete Graph
Definition
A simple graph where every vertex (node) is connected to every vertex
Term
Direct Connections
Definition
A complete graph
Term
Degree of a vertex
Definition
The number of edgtes that connect to it (a loop counts twice)
Term
Total degree of the graph
Definition
The sum of the degree of the vertices
Term
The graph perposition
Definition
In any graph, there is an even number of vertices with an odd number of degrees
Term
Walk
Definition
Teavel from one vertex to another; may repeat
Term
Closed walk
Definition
Walk that starts and ends at the same vertex
Term
Path
Definition
Walk that doesn't repeat any edges
Term
Simple Path
Definition
A path that does not repeat vertices
Term
Circut
Definition
A closed walk that does not repeat edges
Term
Simple circut
Definition
A circut that does not repeat vertices (except @ start / end)
Term
Identity Matrix
Definition

Has 1's down the diagnol; 0's everywhere else.

 

|1 0 0|

|0 1 0|

|0 0 1|

 

Term
Tree
Definition

Connected graph with:

*No circuts

*No isolated vertices 

Term
Terminal Vertex
Definition
Has a degree of 1
Term
Internal Vertex
Definition
Has a degree of > 1
Term
Isomorphic
Definition
Has the same structure
Term
Root
Definition
A vertex from which all others "hang" (identified starting area
Term
Child
Definition
An adjacent node below the node (vertex) of interest
Term
Parent
Definition
The adjacent node above the vertex (node) of interest
Term
Descendents
Definition
All vertices directly below the vertex of interest
Term
Binary Tree
Definition
A rooted tree where each vertex has at most 2 children
Term
Full Binary Tree
Definition
Every internal vertex (including the root) has exactly 2 children (no 1 child)
Term
Spanning Tree
Definition

a subgraph that contains every vertex in the original connected graph

(Make a tree out of a graph) 

Term
Minimal Spanning Tree
Definition
A spanning tree with the least total (weight/cost); Needs weights associated with it
Term
Adjacency Matrix
Definition
Tells how many edges go from one vertex to another
Term
Pigenhole Principle
Definition
Given m pigeonholes and n pigeons when n > m, then one pigeonhole must have at least two pigeons.
Term
Composition of functions
Definition
The result of one function can be the input of a second function
Term
Relation
Definition
An association between data terms
Term
Cardinality
Definition
The number of elements in a set
Supporting users have an ad free experience!