이산수학 정리2

트리
부모는 무조건 1개
자식은 없을수도 있고 있을수도 있고
형제노드 같은높이의 노드
차수=선의 수=자식수
트리의 차수= 각 차수중에 가장 큰 녀석
리프노트=단말노드=터미널노드=자식이없는애들
내부노드=리프노드 제외한 애들 (루트노드 포함)
트리의 무게=리프노드들의 수
완전이진트리=무조건 왼쪽부터 채움.!!! 2개씩 아니여도됨
포화이진트리=완전가득찬 트리
sruskal알고리즘=가중치 작은것부터.
prim알고리즘=임의의 꼭지점부터!

행벡터= 1Xn행렬
열벡터= mX1행렬
A+0행렬=A

형렬의 합=같은 크기끼리만 가능
행렬의 차=같은 크기끼리만 가능
스칼라곱=같은 크기끼리만 가능 k실수를 곱한것.
합 = 교환,결합,항등원,역원

스칼라곱 과 형렬의 곱= 결합,분배가능   하지만!!! 분배법칙 안됨.

행렬의 곱=mn행렬 곱하기 nl행렬이면 ml행렬이 나옴.
앞의 열의갯수(n)과 뒤의 행(n)의 갯수가 같아야지 가능함!!!

0행렬을 곱하지 않아도 0행렬이 나올수 있다.
가우스소거법=행렬이 될수 있다.

행사다리골(행제형) 조건3개

-0행이 아닌 행은 영행 위에 있다

-0행이 아닌 형의 첫번째 0이 아닌 원소를 선도원소라 하는데 , 모든 선도원소는 1이다

-주어진 행의 선도원소는 아래행의 선도원소보다 왼쪾에 있어야한다.

기약 행사다리골(소거 행제형)=가우스조르단소거법

위에 3개에다가 아래 1개를 추가한것.

-선도원소가 포함된 열(세로)에서 선도원소를 제외한 모든원소는 0이다.

정방행렬= 정방행렬 = 스퀘어 매트릭스=n차 정방행렬=차수=3X3행렬 이런거..=대각원소=주대각

단위행렬= 정방행렬 =유닛매트릭스=대각원소가 모두1 나머지가 모두0

대각행렬= 정방행렬 =대각원소이외의 모든원소가 0인 행렬=대각원소가 0이어도됨. 즉 0행렬도 대각행렬임.=즉 대각은 뭐든 상관없고 나머지가  0인것임.

대칭행렬= 정방행렬  =대각선을 기준으로 양옆?이 같은것들.(1시방향애들과 7시방향애들이 같은것),대각선은 뭐듣 상관없음.

교대행렬=대각선은모두0, 나머지는 +- 부호 반대로된것

삼각행렬
-상삼각행렬=주대각 아래가 모두 0= 위아래 모두 0이어도됨
-하삼각행렬=주대각 위가 모두 0 = 위아래 모두가 0 이어도됨

전치행렬=행과 열을 바꿔치는것. 즉 가로를 세로로 세워서 만드는것들.

부울행렬= 모든원소가 0or1만 있는 행렬
부울 합=or
부울 교차=and
부울 곱=익스클루시브 or  = (A and B)or (AandB)

함수
E! =느낌표가 있으면 딱 1개만 존재한다는 것임.
함수란 무엇인가?
모든 x에 대해서 딱1개만 y로 가는것.  1개에서 2개로 화살표가 가면안됨!! 무조건 1개로만 가야함.

 관계에서 함수더라고 역관계에서는 안될수가 있다.

전사함수=x와 y가 같음 왼쪽(x)에 남는게 없는것. y에 남는게 없는것 모두사용 x도 모두사용

 단사함수=x1->y1과 x2->y2가 있을떄 y1과 y2가 같으면 x1과 x2도 같다. 왼족과 오른쪾이 하나씪만 가도록. 2개로 가면안됨왼쪽(x)에 남는게 없는것. y는 남아도됨. 그리고 1개씪만 출발해야함. 1개씪만 도착해야함.