Fourth Woods Wiki

User Tools

Site Tools

Trace:
discrete_math

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
discrete_math [2011/09/14 03:43] – javapimpdiscrete_math [2023/08/18 18:15] (current) – external edit 127.0.0.1
Line 11: Line 11:
 `G = (:{1,2,3,4,5,6}, {a,b,c,d,e}, {(a, 2-3), (b, 1-4), (c, 4-5), (d, 1-3), (e, 2-2)}:)` `G = (:{1,2,3,4,5,6}, {a,b,c,d,e}, {(a, 2-3), (b, 1-4), (c, 4-5), (d, 1-3), (e, 2-2)}:)`
  
-%%(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure1.png]%%+<diag> 
 +{"diag":{"width":"320","height":"240","elements":[{"text":{"center":{"x":238,"y":120},"text":"6","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":98,"y":153},"text":"5","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":22,"y":182},"text":"4","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":183,"y":174},"text":"3","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":192,"y":79},"text":"2","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":28,"y":31},"text":"1","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":175,"y":67}}},{"vertex":{"point":{"x":175,"y":152}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":33,"y":166}}},{"vertex":{"point":{"x":90,"y":143}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":31,"y":52}}},{"vertex":{"point":{"x":173,"y":154}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":30,"y":54}}},{"vertex":{"point":{"x":30,"y":165}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":185,"y":113},"text":"a","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":21,"y":100},"text":"b","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":62,"y":162},"text":"c","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":112,"y":92},"text":"d","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":150,"y":34},"text":"e","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":176,"y":46}}},"radius":20,"lineWidth":2,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":177,"y":68}}},"radius":5,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":233,"y":105}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":174,"y":156}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":89,"y":142}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":30,"y":167}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":29,"y":50}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}}]}} 
 + 
 +</diag> 
 + 
 +  * //Adjacent nodes// - nodes that are connected by an arc. 
 +  * //Loop// - an arc that starts and ends with the same node. 
 +  * //Loop free graph// - graph with no loops. 
 +  * //Isolated node// - a node not adjacent to any other node. 
 +  * //Degree// - the number of arcs that end at a node. 
 +  * //Parallel arcs// - two arcs with the same endpoints. 
 +  * //Simple// - has no parallel arcs and no loops. 
 +  * //Complete graph// - all distinct nodes are adjacent (always connected). 
 +  * //Path// - a sequence of consecutive arcs in a graph. 
 +  * //Path length// - the number of arcs in the path. 
 +  * //Connected graph// - there is a path to every node in the graph. 
 +  * //Cycle// - a path exists from a node back to the same node such that no arc is used more than once. 
 +  * //Acyclic// - has no cycles.
  
-;Adjacent nodes:nodes that are connected by an arc. 
-;Loop:an arc that starts and ends with the same node. 
-;Loop free graph:graph with no loops. 
-;Isolated node:a node not adjacent to any other node. 
-;Degree:the number of arcs that end at a node. 
-;Parallel arcs:two arcs with the same endpoints. 
-;Simple:has no parallel arcs and no loops. 
-;Complete graph:all distinct nodes are adjacent (always connected). 
-;Path:a sequence of consecutive arcs in a graph. 
-;Path length:the number of arcs in the path. 
-;Connected graph:there is a path to every node in the graph. 
-;Cycle:a path exists from a node back to the same node such that no arc is used more than once. 
-;Acyclic:has no cycles. 
-;Tree:a graph that is connected and acyclic (including loops). 
-\\ 
-%%(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure2.png]%% 
-\\ 
-* Node 1 is the starting node (or root node). 
-* Node 1 is the parent node. 
-* Nodes 2 and 3 are children of 1. 
-* Nodes 4, 5, and 6 are children of 2. 
-* Nodes 7 and 8 are children of 3. 
-\\ 
-* a and b are branches. 
-\\ 
-;Leaves:nodes with no children. 
-;Internal nodes:nodes that are non-leaves. 
-;Node depth:the length of the path from the root to the node. 
-;Height:the greatest depth. 
-\\ 
-A __binary tree__ is a tree where each node has at most two children. 
-\\ 
-%%(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure3.png]%% 
-\\ 
-A __full binary tree__ is a binary tree where all internal nodes have two children and all leaves of the tree are at the same depth. 
-\\ 
-%%(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure4.png]%% 
-\\ 
-''__Theorem__ - a tree with `n` nodes has `(n - 1)` arcs.'' 
-!!Undirected Graphs 
 ---- ----
 +
 +//Tree// - a graph that is connected and acyclic (including loops).
 +
 +  * //Leaves// - nodes with no children.
 +  * //Internal nodes// - nodes that are non-leaves.
 +  * //Node depth// - the length of the path from the root to the node.
 +  * //Height// - the greatest depth.
 +
 +<diag>
 +{"diag":{"width":"300","height":"200","elements":[{"text":{"center":{"x":127,"y":24},"text":"1","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":65,"y":47},"text":"2","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":20,"y":128},"text":"4","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":189,"y":54},"text":"3","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":67,"y":130},"text":"5","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":106,"y":130},"text":"6","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":148,"y":122},"text":"7","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":224,"y":118},"text":"8","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":177,"y":172},"text":"9","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":126,"y":40}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":66,"y":68}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":20,"y":111}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":175,"y":65}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":66,"y":112}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":105,"y":113}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":155,"y":111}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":207,"y":109}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":172,"y":154}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":127,"y":41}}},{"vertex":{"point":{"x":69,"y":68}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":128,"y":42}}},{"vertex":{"point":{"x":173,"y":63}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":65,"y":69}}},{"vertex":{"point":{"x":22,"y":110}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":66,"y":71}}},{"vertex":{"point":{"x":66,"y":111}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":69,"y":70}}},{"vertex":{"point":{"x":104,"y":112}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":176,"y":67}}},{"vertex":{"point":{"x":156,"y":110}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":176,"y":66}}},{"vertex":{"point":{"x":207,"y":109}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":155,"y":112}}},{"vertex":{"point":{"x":171,"y":153}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":96,"y":46},"text":"a","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":154,"y":44},"text":"b","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":38,"y":83},"text":"c","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":61,"y":96},"text":"d","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":95,"y":88},"text":"e","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":157,"y":86},"text":"f","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":198,"y":79},"text":"g","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":160,"y":140},"text":"h","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}}]}}
 +</diag>
 +
 +  * Node 1 is the starting node (or root node).
 +  * Node 1 is the parent node.
 +  * Nodes 2 and 3 are children of 1.
 +  * Nodes 4, 5, and 6 are children of 2.
 +  * Nodes 7 and 8 are children of 3.
 +  * a and b are branches.
 +
 +----
 +
 +A //binary tree// is a tree where each node has at most two children.
 +
 +<diag>
 +{"diag":{"width":"250","height":"140","elements":[{"text":{"center":{"x":127,"y":24},"text":"1","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":26,"y":82},"text":"2","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":219,"y":88},"text":"3","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":126,"y":40}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":34,"y":97}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":205,"y":96}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":127,"y":41}}},{"vertex":{"point":{"x":34,"y":96}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":128,"y":42}}},{"vertex":{"point":{"x":204,"y":95}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":75,"y":60},"text":"a","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":177,"y":61},"text":"b","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":53,"y":113},"text":"left child","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":203,"y":111},"text":"right child","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}}]}}
 +</diag>
 +
 +
 +A //full binary tree// is a binary tree where all internal nodes have two children and all leaves of the tree are at the same depth.
 +
 +<diag>
 +{"diag":{"width":"280","height":"140","elements":[{"text":{"center":{"x":127,"y":24},"text":"1","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":65,"y":47},"text":"2","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":31,"y":124},"text":"4","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":189,"y":54},"text":"3","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":97,"y":122},"text":"5","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":153,"y":124},"text":"6","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":220,"y":118},"text":"7","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":126,"y":40}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":66,"y":68}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":35,"y":111}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":175,"y":65}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":91,"y":111}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":152,"y":109}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"circle":{"center":{"vertex":{"point":{"x":207,"y":109}}},"radius":4,"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":127,"y":41}}},{"vertex":{"point":{"x":69,"y":68}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":128,"y":42}}},{"vertex":{"point":{"x":173,"y":63}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":65,"y":69}}},{"vertex":{"point":{"x":35,"y":109}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":69,"y":70}}},{"vertex":{"point":{"x":91,"y":111}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":176,"y":67}}},{"vertex":{"point":{"x":153,"y":109}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"line":{"vertices":[{"vertex":{"point":{"x":176,"y":66}}},{"vertex":{"point":{"x":207,"y":109}}}],"lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#ffffff","fontFace":"Ariel","fontHeight":20,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":96,"y":46},"text":"a","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":154,"y":44},"text":"b","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":38,"y":83},"text":"c","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":94,"y":83},"text":"d","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":156,"y":82},"text":"e","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}},{"text":{"center":{"x":196,"y":79},"text":"f","lineWidth":1,"lineStyle":"solid","lineColor":"#000000","fillColor":"#000000","fontFace":"Courier","fontHeight":10,"fontStyle":"normal","rotation":0}}]}}
 +</diag>
 +
 +__//Theorem//__ - a tree with `n` nodes has `(n - 1)` arcs.
 +==== Undirected Graphs ====
  
 `G = (:N, A, f :)` `G = (:N, A, f :)`
-\\ +
-\\+
 `G = (:{a, b, c}, {1, 2}, {(1, a-c), (2, c-b)}:)` `G = (:{a, b, c}, {1, 2}, {(1, a-c), (2, c-b)}:)`
-\\ 
  
 This graph is described as: the set of nodes, `a`, `b` and `c`; the set of arcs, `1` and `2`; arc `1` spans nodes `a` and `c`, arc `2` spans nodes `c` and `b`. This graph is described as: the set of nodes, `a`, `b` and `c`; the set of arcs, `1` and `2`; arc `1` spans nodes `a` and `c`, arc `2` spans nodes `c` and `b`.
-\\ 
  
-%%(margin-left:50px)[http://192.168.1.110/wiki/attach/Discrete%20Math/figure5.png]%% +{{:figure5.png?100|Figure 5}} 
-!!Directed Graphs + 
-----+==== Directed Graphs ====
  
 Directed graphs are identified by a function that associates an arc with an __ordered pair__ of nodes. Directed graphs are identified by a function that associates an arc with an __ordered pair__ of nodes.
-\\ 
  
 `G = (:{a, b, c}, {1, 2}, {(1, (a, c)), (2, (c, b))}:)` `G = (:{a, b, c}, {1, 2}, {(1, (a, c)), (2, (c, b))}:)`
-\\ 
  
 This graph is described as: the set of nodes, `a`, `b` and `c`; the set of arcs, `1` and `2`; arc `1` is directed from node `a` to node `c`, arc `2` is directed from node `c` to node `b`. This graph is described as: the set of nodes, `a`, `b` and `c`; the set of arcs, `1` and `2`; arc `1` is directed from node `a` to node `c`, arc `2` is directed from node `c` to node `b`.
-\\ 
  
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure6.png' style='margin-left:50px' }] +{{:figure6.png?100|Figure 6}} 
-\\ + 
-;Initial node:the node from which an arc begins. +  * //Initial node// - the node from which an arc begins. 
-;Terminal node:the node where an arc ends. +  * //Terminal node// - the node where an arc ends. 
-;Adjacent node:in a directed graph, node `b` is adjacent to node `a` if there is an arc from node `a` to node `b`. +  * //Adjacent node// - in a directed graph, node `b` is adjacent to node `a` if there is an arc from node `a` to node `b`. 
-;Inverted arc:if there is an arc from node `a` to node `b`, an inverted arc would produce the opposite association from node `b` to node `a`.+  * //Inverted arc// - if there is an arc from node `a` to node `b`, an inverted arc would produce the opposite association from node `b` to node `a`. 
 + 
 +{{:figure7.png?150 |Figure 7}}
  
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure7.png' style='margin-left:50px' }] 
 Attributes of this graph: Attributes of this graph:
-* Nodes `b` and `c` are adjacent to node `a`. Node `a` is not adjacent to nodes `b` and `c`. +  * Nodes `b` and `c` are adjacent to node `a`. Node `a` is not adjacent to nodes `b` and `c`. 
-* Node `a` is adjacent only to node `d`. +  * Node `a` is adjacent only to node `d`. 
-* Arc `5` is the only loop. +  * Arc `5` is the only loop. 
-* Arcs `2`, `3` and `4` form a cycle. +  * Arcs `2`, `3` and `4` form a cycle. 
-* The degree of node `a` is 3; 2 arcs out, 1 arc in.+  * The degree of node `a` is 3; 2 arcs out, 1 arc in. 
 \\ \\
-;Parallel arcs:arcs that have the same initial node and same terminal node. 
 \\ \\
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure8.png' style='margin-left:50px' }] 
 \\ \\
-;Complete graph:all distinct nodes are adjacent. +
-\\ +
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure9.png' style='margin-left:50px' }] +
-\\ +
-;Connected graph:a path exists from any node to any other node. +
-\\ +
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure10.png' style='margin-left:50px' }] +
-!!Adjacency Matrices+
 ---- ----
-;Adjacency matrix:the number of arcs from one node to another node.+ 
 +Parallel arcs - arcs that have the same initial node and same terminal node. 
 + 
 +{{:figure8.png?150|Figure 8}} 
 + 
 +Complete graph - all distinct nodes are adjacent. 
 + 
 +{{:figure9.png?300|Figure 9}} 
 + 
 +Connected graph - a path exists from any node to any other node. 
 + 
 +{{:figure10.png?200|Figure 10}} 
 + 
 +==== Adjacency Matrices ==== 
 + 
 +//Adjacency matrix//  - the number of arcs from one node to another node. 
 An adjacency matrix describes which nodes in a graph are adjacent to which other nodes. An adjacency matrix describes which nodes in a graph are adjacent to which other nodes.
-\\ +
-\\+
 `G = (:{a, b, c}, {1, 2}, {(1, a-b), (2, b-c)}:)` `G = (:{a, b, c}, {1, 2}, {(1, a-b), (2, b-c)}:)`
-\\ + 
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure11.png' style='margin-left:50px' }] +{{:figure11.png?150|Figure 11}} 
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure12.png' style='margin-left:50px' }] +{{:figure12.png?200|Figure 12}} 
-\\+
 Matrix dimensions are the number of rows by the number of columns. Matrix dimensions are the number of rows by the number of columns.
-\\+
 E.g. 2 rows X 3 columns: `[(1, 0, 1),(0, 1, 1)]` E.g. 2 rows X 3 columns: `[(1, 0, 1),(0, 1, 1)]`
-\\+
 An adjacency matrix always has the same number of rows as columns. An adjacency matrix always has the same number of rows as columns.
-\\ + 
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure13.png' style='margin-left:50px' }] +{{:figure13.png?200|Figure 13}} 
-\\+
 The __main diagonal__ runs from the upper left to lower right corners of the matrix. The main diagonal will always have 0's in each position unless the graph has a loop. A loop in the graph will be indicated by a 1 on the main diagonal. The __main diagonal__ runs from the upper left to lower right corners of the matrix. The main diagonal will always have 0's in each position unless the graph has a loop. A loop in the graph will be indicated by a 1 on the main diagonal.
-\\+
 For a __symmetric matrix__, each side of the main diagonal is a mirror image of the other. For a __symmetric matrix__, each side of the main diagonal is a mirror image of the other.
-\\+
 An undirected graph always has a symmetric adjacency matrix. An undirected graph always has a symmetric adjacency matrix.
  
-!!Matrix Multiplication +==== Matrix Multiplication ==== 
----- + 
-;Square Matrix:a matrix with the same number of rows and columns. +  * //Square Matrix// - a matrix with the same number of rows and columns. 
-;Zero Matrix:a matrix with all zeros. +  * //Zero Matrix// - a matrix with all zeros. 
-\\+
 `[(0, 0, 0),(0, 0, 0)]` `[(0, 0, 0),(0, 0, 0)]`
-\\ + 
-;Identity Matrix:a matrix with all 1'a along the main diagonal with 0's in all other positions. An identity matrix must be square. +//Identity Matrix//  - a matrix with all 1'a along the main diagonal with 0's in all other positions. An identity matrix must be square. 
-\\ + 
-Identity matrix: `I = [(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)]&nbsp;4 xx 4` +Identity matrix: `I = [(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)] 4 xx 4` 
-\\ + 
-\\ +Not identity matrix: `[(1, 0, 0, 0), (0, 1, 0, 0)] 2 xx 4` 
-Not identity matrix: `[(1, 0, 0, 0), (0, 1, 0, 0)]&nbsp;2 xx 4` +
-\\ +
-\\+
 `I * A = A` `I * A = A`
-\\ +
-\\+
 Matrix multiplication is NOT commutative. Order does make a difference. Matrix multiplication is NOT commutative. Order does make a difference.
-\\+
 `A * B != B * A` `A * B != B * A`
-!Scalar multiplication of matrices+=== Scalar multiplication of matrices === 
 `2 * [(a_(11), a_(12)), (a_(21), a_(22))] = [(2 * a_(11), 2 * a_(12)), (2 * a_(21), 2 * a_(22))]` `2 * [(a_(11), a_(12)), (a_(21), a_(22))] = [(2 * a_(11), 2 * a_(12)), (2 * a_(21), 2 * a_(22))]`
-!Product of matrices+=== Product of matrices === 
 `A * B = C` `A * B = C`
-\\+
 The number of columns in `A` must be the same as the number of rows in `B` to multiply. The number of columns in `A` must be the same as the number of rows in `B` to multiply.
-\\ + 
-`&nbsp;A&nbsp;&nbsp;*&nbsp;&nbsp;B&nbsp;&nbsp;=&nbsp;&nbsp;C` +`2xx3 * 3xx4 = 2xx4` 
-\\ +
-`2xx3&nbsp;&nbsp;3xx4&nbsp;&nbsp;&nbsp;2xx4` +
-\\ +
-\\+
 amath amath
 [(a_(11), a_(12)), (a_(21), a_(22))] * [(a_(11), a_(12)), (a_(21), a_(22))] *
Line 168: Line 179:
 endamath endamath
  
-Adjacency Matrices (cont.)+==== Adjacency Matrices (cont.) ====
  
 Given the following graph: Given the following graph:
-\\+
 `G = (:{a, b, c}, {1, 2}, {(1, a-b), (2, b-c)}:)` `G = (:{a, b, c}, {1, 2}, {(1, a-b), (2, b-c)}:)`
-\\ + 
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure11.png' style='margin-left:50px' }] +{{:figure11.png?150|Figure 14a}} 
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure14.png'}] +{{:figure14.png?200|Figure 14b}} 
-\\ +
-\\+
 `A * A = A^2 = [(0, 1, 0), (1, 0, 1), (0, 1, 0)] * [(0, 1, 0), (1, 0, 1), (0, 1, 0)] = `A * A = A^2 = [(0, 1, 0), (1, 0, 1), (0, 1, 0)] * [(0, 1, 0), (1, 0, 1), (0, 1, 0)] =
 [(0*0+1*1+0*0, 0*1+1*0+0*1, 0*0+1*1+0*0),(1*0+0*1+1*0, 1*1+0*0+1*1, 1*0+0*1+1*0), (0*0+1*1+0*0, 0*1+1*0+0*1, 0*0+1*1+0*0)] = [(0*0+1*1+0*0, 0*1+1*0+0*1, 0*0+1*1+0*0),(1*0+0*1+1*0, 1*1+0*0+1*1, 1*0+0*1+1*0), (0*0+1*1+0*0, 0*1+1*0+0*1, 0*0+1*1+0*0)] =
 [(1, 0, 1), (0, 2, 0), (1, 0, 1)]` [(1, 0, 1), (0, 2, 0), (1, 0, 1)]`
-\\ + 
-\\ +{{:figure15.png?200|Figure 15}} 
-[{Image src='http://192.168.1.110/wiki/attach/Discrete%20Math/figure15.png'}] +
-\\ +
-\\+
 `A` represents the number of paths of length 1. `A` represents the number of paths of length 1.
-* There is one path from node `a` to node `b`. +  * There is one path from node `a` to node `b`. 
-* Likewise, there is one path from node `b` to node `a`. +  * Likewise, there is one path from node `b` to node `a`. 
-* There is one path from node `b` to node `c`. +  * There is one path from node `b` to node `c`. 
-* There is one path from node `c` to node `b`. +  * There is one path from node `c` to node `b`. 
-\\+
 `A^2` represents the number of paths of length 2. `A^2` represents the number of paths of length 2.
-* There is one path of length 2 from node `a` to node `a`. The path traverses from node `a` to node `b` then back to node `a`. +There is one path of length 2 from node `a` to node `a`. The path traverses from node `a` to node `b` then back to node `a`. 
-* There is one path of length 2 from node `c` to node `c`. +  * There is one path of length 2 from node `c` to node `c`. 
-* There are two paths of length 2 from node `b` to node `b`. The first traverses from node `b` to node `a` then back to node `b`. The second traverses from node `b` to node `c` then back to node `b`. +  * There are two paths of length 2 from node `b` to node `b`. The first traverses from node `b` to node `a` then back to node `b`. The second traverses from node `b` to node `c` then back to node `b`. 
-* There is one path of length 2 from node `a` to node `c`. The path traverses from node `a` to node `b` then continues on to node `c`. +  * There is one path of length 2 from node `a` to node `c`. The path traverses from node `a` to node `b` then continues on to node `c`. 
-* There is one path of length 2 from node `c` to node `a`. +  * There is one path of length 2 from node `c` to node `a`. 
-\\+
 `A^n` represents the number of paths of length `n` between any two nodes. `A^n` represents the number of paths of length `n` between any two nodes.
-\\ +
-\\+
 In determining the value of `n`, consider the number of distinct nodes - 1 (not including isolated nodes). In determining the value of `n`, consider the number of distinct nodes - 1 (not including isolated nodes).
-\\+
 `R = A + A^2 + A^3 + ... + A^n` `R = A + A^2 + A^3 + ... + A^n`
-\\ + 
-`R` - The number of paths `<=` length `n`+`R` - The number of paths `\le` length `n`
  
  
discrete_math.1315971831.txt.gz · Last modified: 2023/08/18 18:15 (external edit)