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 [2016/05/14 18:43] – javapimpdiscrete_math [2023/08/18 18:15] (current) – external edit 127.0.0.1
Line 10: Line 10:
  
 `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)}:)`
- 
-{{:figure1.png?200|Figure 1}} 
  
 <diag> <diag>
Line 17: Line 15:
  
 </diag> </diag>
- 
-Same graph using the ditaa plugin: 
- 
-<ditaa noshadow> 
-             /---\ 
- 1           |   | 
- *-------\   |{o}|e 
- |       |   \-*-/ 
- |      d|     |2 
- |       |     | 
- |       |     |a     *-6 
-b|       |     | 
- |       \-----* 
- |             3 
- | 
- *---------* 
- 4    c    5 
-</ditaa> 
  
   * //Adjacent nodes// - nodes that are connected by an arc.   * //Adjacent nodes// - nodes that are connected by an arc.
Line 59: Line 39:
   * //Height// - the greatest depth.   * //Height// - the greatest depth.
  
-{{:figure2.png?200 |Figure 2}}+<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 starting node (or root node).
Line 67: Line 49:
   * Nodes 7 and 8 are children of 3.   * Nodes 7 and 8 are children of 3.
   * a and b are branches.   * a and b are branches.
-\\ 
-\\ 
-Same graph using the graphviz plugin: 
  
-<graphviz dot> 
-digraph { 
-   splines=false; 
-   edge[dir=none, weight=2]; 
-   node[shape=point]; 
-   1 -> 2[label="a", taillabel="1"]; 
-   1 -> 3[label="b"]; 
-   2 -> 4[label="c", taillabel="2", headlabel="4"]; 
-   2 -> 5[label="d", headlabel="5"]; 
-   2 -> 6[label="e", headlabel="6"]; 
-   3 -> 7[label="f", taillabel="3"]; 
-   3 -> 8[label="g", headlabel="8"]; 
-   edge[weight=10]; 
-   7 -> 9[label="h", taillabel="7", headlabel="9"]; 
-} 
-</graphviz> 
 ---- ----
  
 A //binary tree// is a tree where each node has at most two children. A //binary tree// is a tree where each node has at most two children.
  
-{{:figure3.png?300|Figure 3}}+<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. 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.
  
-{{:figure4.png?300|Figure 4}}+<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. __//Theorem//__ - a tree with `n` nodes has `(n - 1)` arcs.
Line 245: Line 213:
 `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.1463251427.txt.gz · Last modified: 2023/08/18 18:15 (external edit)